What is the output for this code? what is the outcome of this algorithm ? def Eu
ID: 3717705 • Letter: W
Question
What is the output for this code?
what is the outcome of this algorithm ?
def Euclidean (a, b):
while (b != 0):
r = a % b
a = b
b = r
return a
def f(x, n):
return (x**2 + 1) % n
def Pollard_rho (n, x):
y = x
trials = 0
while (True):
x = f(x, n)
y = f(f(y, n), n)
trials = trials + 1
gcd = Euclidean((x - y)%n, n)
if (gcd > 1 and gcd < n):
print("# success! found (x, y) =", x, y, " after ", trials, " trials")
return x, y
# now this is faster
n = 785
x, y = Pollard_rho (n,1)
print("# factor of", n, "is ", Euclidean(x-y, n))
print()
Explanation / Answer
Pollard's rho method for factoring. Explain in detail what is going on , on each line?
What is the output for this code? What is the outcome of this algorithm?
Pollard’s Rho is a prime factorization algorithm, particularly fast for a large composite number with small prime factors.
The Rho algorithm was a good choice because the first prime factor is much smaller than the other one.
Concepts used in Pollard’s Rho Algorithm:
1. Let us take Two numbers x and y are said to be congruent modulo n
(x = y modulo n) if
a. their absolute difference is an integer multiple of n, OR,
b. Each of them leaves the same remainder when divided by n.
2. The Greatest Common Divisor is the largest number which divides evenly into each of the original numbers.
3. Birthday Paradox: The probability of two persons having same birthday is unexpectedly high even for small set of people.
4. Floyd’s cycle-finding algorithm: If tortoise and hare start at same point and move in a cycle such that speed of hare is twice the speed of tortoise, then they must meet at some point.
1. Start with random x and c. Take y equal to x and f(x) = x2 + c.
2. While a divisor isn’t obtained
a. Update x to f(x) (modulo n) [Tortoise Move]
b. Update y to f(f(y)) (modulo n) [Hare Move]
c. Calculate GCD of |x-y| and n
d. If GCD is not unity
i. If GCD is n, repeat from step 2 with another set of x, y and c
ii. Else GCD is our answer
def Euclidean (a, b):
//definition of it will return the GCD of Two numbers
while (b != 0):
r = a % b
a = b
b = r
return a //return GCD value
def f(x, n): // it will calculate
return (x**2 + 1) % n // calculate f(x) modulo n.
def Pollard_rho (n, x):
y = x
trials = 0
while (True):
x = f(x, n) //Tortoise Move
y = f(f(y, n), n) // Hare Move
trials = trials + 1
//call GCD method and for function and n
gcd = Euclidean((x - y)%n, n)
if (gcd > 1 and gcd < n):
print("# success! found (x, y) =", x, y, " after ", trials, " trials") return x, y // display the final out put
# now this is faster
n = 785
x, y = Pollard_rho (n,1)
print("# factor of", n, "is ", Euclidean(x-y, n))
print()
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.