wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> putnam exam (pure math) >> Factoring large numbers is easy
        
(Message started by: Eigenray on May 31^st, 2007, 12:52pm)

Title: Factoring large numbers is easy
Post by Eigenray on May 31^st, 2007, 12:52pm

(1) Suppose you are given a function sqrt(a,n), which returns an integer b such that b² http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/equiv.gif a mod n, if it exists. Give an efficient algorithm to factor n.

(2) Suppose you are given a function order(a,n), which returns the smallest positive integer k for which a^k http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/equiv.gif 1 mod n. Give an efficient algorithm to factor n.

Title: Re: Factoring large numbers is easy
Post by Barukh on Jun 22^nd, 2007, 4:31am

For the (1), take a to be a perfect square - that's the basic idea of Dixon's factorization algorithm (http://en.wikipedia.org/wiki/Dixon's_algorithm#Basic_idea).

Title: Re: Factoring large numbers is easy
Post by Eigenray on Jun 22^nd, 2007, 5:04am

on 06/22/07 at 04:31:37, Barukh wrote:

For the (1), take a to be a perfect square - that's the basic idea of Dixon's factorization algorithm (http://en.wikipedia.org/wiki/Dixon's_algorithm#Basic_idea).

Yes. It's also related to [link=http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=riddles_medium;action=display;num=1182011772]this recent problem[/link].

Title: Re: Factoring large numbers is easy
Post by Eigenray on Jul 24^th, 2007, 2:02pm

Hint (sort of): In 1994, [hide]Peter Shor[/hide] discovered that ord(a,n) can actually be computed (with arbitrarily small error probability) in polynomial time ... [hide]on a quantum computer[/hide].

Title: Re: Factoring large numbers is easy
Post by Barukh on Jul 27^th, 2007, 1:56am

Uh?! This "hint" actually gives away the whole solution (http://en.wikipedia.org/wiki/Shor's_algorithm#I._Obtaining_factors_from_period).

So simple...

Title: Re: Factoring large numbers is easy
Post by Eigenray on Jul 27^th, 2007, 6:12am

Well, it was a hint in the sense that it tells you what to look up if you want to look it up. Note that it is similar to part (1), in that you are using the period to find a random square root of 1.

But the Wikipedia entry is missing a key point:

Quote:

If N also does not divide (a^r/2+1), then N must have a nontrivial common factor with each of (a^r/2-1) and (a^r/2+1).

What is the probability that this happens, if we pick a at random? This requires a bit of number theory, and is the reason I put this problem in the putnam section.

In particular, prove that this algorithm does in fact find a non-trivial factor of N with probability > 1-http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/epsilon.gif, in time polynomial in log(N).

Title: Re: Factoring large numbers is easy
Post by Barukh on Jul 30^th, 2007, 3:22am

Quote:

If N also does not divide (a^r/2+1)…

on 07/27/07 at 06:12:05, Eigenray wrote:

What is the probability that this happens, if we pick a at random?

I will consider the case N = pq, p, q odd prime numbers, here.

I will use the following notations:

ord_p(a) – multiplicative order of a modulo p;
T(x) – maximum power of 2 dividing x (i.e. x = 2^T(x)d, d an odd number).

Let T(p-1) = n > 0. I am going to divide the numbers 1, …, p-1 into n+1 classes 0, 1, …, n s.t. number a belongs to class k iff T(ord_p(a)) = k.

Let g be a primitive root modulo p. Then, a = g^s for some s < p. Let’s count the numbers s with T(s) = k. Consider two cases:

1. k http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/le.gif n, then T(ord_p(a)) = n-k (why?), and there are (p-1)/2^k+1 of these.
2. k > n. Then T(ord_p(a)) = 0, and there are (p-1)/ 2ⁿ⁺¹ of these.

In any case, the number of elements in class k doesn’t exceed p/2.

Getting back to N = pq: If N divides a^r/2+1, that means both p, q divide it. That is, p, q both divide a^r-1, but not a^r/2-1. Therefore, T(ord_p(a)) = T(ord_q(a)).

Picking a at random modulo N, let’s fix k = T(ord_p(a)). Then, the probability that T(ord_q(a)) = k won’t exceed 1/2.

So, the number that leads to a non-trivial factor is chosen with probability > 1/2.

Title: Re: Factoring large numbers is easy
Post by Eigenray on Jul 30^th, 2007, 5:16am

Exactly. The argument generalizes easily to any odd N, since Z_N^* = C₁ x ... x C_r is a product of cyclic groups is all that is used.

In fact, we can compute the probability of failure exactly: given that a is relatively prime to N, the algorithm fails exactly when T(|a₁|) = ... T(|a_r|) = t, for some t, where |a_i| represents the order of a projected into the cyclic group C_i. When t=0, the probability of this is

http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/prod.gif1/2^T_i,

where T_i = T(|C_i|). For 0 < t http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/le.gif m = min(T₁,...,T_r), the probability is

http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/prod.gif1/2^T_i-t+1.

Altogether, the probability of failure is

P = 2^-S[1 + (2^rm-1)/(2^r-1)] = [2^rm + 2^r - 2]/[2^S(2^r-1)]

where S=http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/sum.gifT_i. Since S http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/ge.gif rm http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/ge.gif r, we have

P http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/le.gif [2^rm + 2^r - 2]/[2^rm(2^r-1)] http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/le.gif 1/2^r-1.

Of course, the algorithm fails when r=1.

Title: Re: Factoring large numbers is easy
Post by BenVitale on Feb 20^th, 2008, 1:57pm

Eigenray wrote:

(1) Suppose you are given a function sqrt(a,n), which returns an integer b such that b^2 = a mod n, if it exists. Give an efficient algorithm to factor n.
..................................
I use a theorem which is derived from the one below.

Theorem:

For any positive integer N, suppose there exists an integer A such that
A^x=1(modN) for some integer x. If q is a prime divisor of x such that A^(x/q) =/= 1(modN),
and if there exists a prime divisor p of N, such that q does not divide p-1, then
GCD(A^(x/q) -1(modN), N) =/= 1

Can you prove the above

So basically if we were to find k(=order(a,n)), and q is some prime divisor of k (if k is prime than we can just divide it by itself), then the above thereom says that as long as there exists a prime divisor p of n such that q=/=p-1, then gcd(A^(x/q) -1(modn), n) will give us a nontrivial factor of n.

Title: Re: Factoring large numbers is easy
Post by Eigenray on Feb 20^th, 2008, 3:20pm

on 02/20/08 at 13:57:59, BenVitale wrote:

For any positive integer N, suppose there exists an integer A such that
A^x=1(modN) for some integer x. If q is a prime divisor of x such that A^(x/q) =/= 1(modN),
and if there exists a prime divisor p of N, such that q does not divide p-1, then
GCD(A^(x/q) -1(modN), N) =/= 1

Can you prove the above

Yes. Suppose p | N but GCD(A^x/q-1, N) = 1. Then A^x/q http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/ne.gif 1 mod p. Since A^x = 1 mod p, it follows that A^x/q mod p has order q, and therefore q | p-1.

Quote:

So basically if we were to find k(=order(a,n)), and q is some prime divisor of k (if k is prime than we can just divide it by itself), then the above thereom says that as long as there exists a prime divisor p of n such that q=/=p-1, then gcd(A^(x/q) -1(modn), n) will give us a nontrivial factor of n.

But consider for example n=85. For any A relatively prime to n, k=order(A,n) is a power of 2, but all prime divisors of n are 1 mod 2. So gcd(A^k/2-1, n) is not guaranteed to be non-trivial. Of course there's still a good chance that it is, but not because of that theorem.

Title: Re: Factoring large numbers is easy
Post by BenVitale on Feb 20^th, 2008, 9:04pm

Eigenray,

The theorem doesn't apply to this example because 2 divides p-1 for every prime factor p of 85.
Remember, we only have that gcd(A^k/q - 1, n) nontrivial if there exists at least one prime factor p
of n such that q=\=p-1. In your example, there are none.

Note: Situations like your example are very rare. Most often we can always find numbers that will
satisfy the conditions of the theorem (and even if we can't, its still likely that gcd(A^k/2 - 1, n)
will be nontrivial anyway).
Quote:

[/quote][quote]

[quote][/quote]

Title: Re: Factoring large numbers is easy
Post by Eigenray on Feb 20^th, 2008, 9:49pm

on 02/20/08 at 21:04:21, BenVitale wrote:

The theorem doesn't apply to this example

Yes, that was my point. I was demonstrating why the theorem doesn't prove that your algorithm will always work.

If you click the 'quote' link, the message text box should start out with text that looks like:

[quote author=... ]Text to quote
[/quote]

Then just write your reply after the [/quote] tag (you can also trim the text between the tags to include only what you're replying to).