23 lines
330 B
Python
23 lines
330 B
Python
|
#!/usr/bin/python
|
||
|
|
import math
|
||
|
|
|
||
|
|
|
||
|
|
def rho(n):
|
||
|
|
x = 3
|
||
|
|
y = 3
|
||
|
|
d = 1
|
||
|
|
while d<=1:
|
||
|
|
x = (x * x + 23) % n
|
||
|
|
y = (y * y + 23) % n
|
||
|
|
y = (y * y + 23) % n
|
||
|
|
d = math.gcd(x-y,n)
|
||
|
|
return d
|
||
|
|
|
||
|
|
|
||
|
|
def main():
|
||
|
|
result = rho(1364593)
|
||
|
|
print(f"p = {result}")
|
||
|
|
|
||
|
|
|
||
|
|
if __name__ == '__main__':
|
||
|
|
main()
|