wu :: forums - Print Page


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

        riddles >> hard >> Pseudoprimes
        
(Message started by: BenVitale on Feb 18^th, 2008, 2:15pm)

Title: Pseudoprimes
Post by BenVitale on Feb 18^th, 2008, 2:15pm

Suppose that we suspect that a number N is a Carmichael number, and we want
to prove this.

Questions:

a) Is there an efficient way of doing this without having to factorize N and proving that p-1 divides N-1 for every prime divisor of n?
b) If the most efficient method does involve factorizing N, then do we need
to know the factorization of N-1 as well?
c) What is the largest known Carmichael number to date?

Title: Re: Pseudoprimes
Post by BenVitale on Feb 18^th, 2008, 2:18pm

Could we just factor it, factoring Charmichael numbers is easy, right?
To do so, let N be the Charmichael number and pick a random A<N.
We know that N | A^(N-1)-1 = (A^((N-1)/2))-1)*(A^((N-1)/2)+1),
so it is likely that GCD(N, A^((N-1)/2)-1) is a nontrivial factor of N.
Do this for many A and obtain a complete factorization.

A much quicker way to factorize it is to pick a subset of factors of N-1 (N-1 will always be easier to factor than N). Then pick a number A, and prime p of the subset from N-1, and compute gcd(A^((N 1)/p) -1,N)=B.

This will almost always be greater than 1.

From here, factor the number N/B using the Pollard rho factoring method, using the iterating function x^(2p) +1 (where p is the prime number used in
the gcd above).

Repeat the above process a few times over (using different primes of N-1) if necessary to give a complete factorization of N.

Question (c) :

'Sufficiently large' has a very specific meaning. If a statement is true for sufficiently large n, it means that there exists some integer M such that the statement is true for all n > M.

However, 'large' can also mean 'arbitrarily large'. The article in Wolfram MathWorld takes the second meaning of 'large'

http://mathworld.wolfram.com/CarmichaelNumber.html

And there's also an article I've found on the web:

A new algorithm for constructing large Carmichael numbers

http://www.ams.org/mcom/1996-65-214/S0025-5718-96-00692-8/S0025-5718-96-00692-8.pdf

What do you think?

Title: Re: Pseudoprimes
Post by Eigenray on Feb 19^th, 2008, 12:47pm

on 02/18/08 at 14:18:12, BenVitale wrote:

This is close, but you have to go further. You could have A^(N-1)/2 = 1 mod N for all A relatively prime to N, for example with N=561, A⁸⁰ = 1 mod N for all A relatively prime to N. Then you wouldn't get any non-trivial factors.

Recall the [link=http://en.wikipedia.org/wiki/Miller-Rabin_primality_test]Miller-Rabin[/link] test: write N-1 = 2^sd, pick a random A, and if A^d http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/ne.gif 1 mod N, and A^{2^r d} http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/ne.gif -1 mod N, for r=0,...,s-1, then N is composite. A random A will work with probability at least 1/4, if N is composite.

In general, this test doesn't actually give a factor of N. But suppose we have such an A as above, proving N is composite. There are two cases: if A^N-1 http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/ne.gif 1 mod N, then N is not Carmichael. On the other hand, if A^N-1 = 1 mod N, consider the smallest r for which A^{2^(r+1) d} = 1 mod N. Then r http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/le.gif s-1, since A^N-1=1 mod N, and r http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/ge.gif 0, since A^d http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/ne.gif 1 mod N. So we must have x = A^{2^r d} http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/ne.gif http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/pm.gif1 mod N, but x² = 1 mod N. Then N divides neither x+1 nor x-1, while N | x²-1, so either (N,x-1) or (N,x+1) is a non-trivial factor of N.

So if N is Carmichael, then a random A will yield a factor of N with probability at least 1/4, so we can very efficiently factor N non-trivially. But this still leaves the problem of factoring the two results again, since neither one is likely to be Carmichael.

[link=http://www.ocf.berkeley.edu/%7Ewwu/cgi-bin/yabb/YaBB.cgi?board=riddles_putnam;action=display;num=1180641167]This thread is related[/link]: if we can factor N-1, then we can find periods mod N, since if N is Carmichael they must all divide N-1, and we can just walk down the lattice of divisors of N-1 to find the period. And if we can find periods mod N, we can find a non-trivial factor of N.

Title: Re: Pseudoprimes
Post by BenVitale on Feb 20^th, 2008, 2:05pm

Eigenray wrote:

"But this still leaves the problem of factoring the two results again, since neither one is likely to be Carmichael."

If we let r=gcd(A^(x/q) -1(modn), n), then it can be shown that n/r will either be a prime number (which usualy will be the case) or if n/r is composite, then every prime divisor p of n/r is such that q divides p-1, which means we can factor n/r using the Pollard rho factoring method with a very fast iterating function.

[ Are you familiar with this result? ]

Eigenray wrote:

"if we can factor N-1, then we can find periods mod N, since if N is Carmichael they must all divide N-1,

and we can just walk down the lattice of divisors of N-1 to find the period.

And if we can find periods mod N, we can find a non-trivial factor of N."

............................................................
Unfortunately, N-1 has a ton of divisors (even more so than N), however this method works
alright for finding the prime divisors of N which are smooth.

Title: Re: Pseudoprimes
Post by BenVitale on Feb 20^th, 2008, 2:16pm

Eigenray wrote:

"if we can factor N-1, then we can find periods mod N, since if N is Carmichael they must all divide N-1,

and we can just walk down the lattice of divisors of N-1 to find the period.

And if we can find periods mod N, we can find a non-trivial factor of N."

............................................................................
The good news is that if we ignore the time it takes to factor N-1, then this method can be shown to take logorithmic time to factor N, hence making it a useful factoring method.

The bad news is that it can sometimes be take very long to obtain a full factorization of N-1 when N isn't smooth. On the other hand, if we only factor out the small prime divisors of N-1 (and luckily for Carmichael numbers, there will be many small prime factors), then we can use these to obtain the prime factors of N which are smooth via the method you described.

Title: Re: Pseudoprimes
Post by Eigenray on Feb 20^th, 2008, 2:55pm

on 02/20/08 at 14:05:06, BenVitale wrote:

If we let r=gcd(A^(x/q) -1(modn), n), then it can be shown that n/r will either be a prime number (which usualy will be the case) or if n/r is composite, then every prime divisor p of n/r is such that q divides p-1

Yes, because A^x/q mod p has order q (assuming n is squarefree; otherwise we could also have p=q).

Quote:

which means we can factor n/r using the Pollard rho factoring method with a very fast iterating function

Why?

Title: Re: Pseudoprimes
Post by Icarus on Feb 20^th, 2008, 7:13pm

Sorry for the unrelated post, but I'm curious: BenV., is there some reason you do this manual quoting instead of using the "Quote" links in the upper right of each post?

Title: Re: Pseudoprimes
Post by BenVitale on Feb 20^th, 2008, 8:04pm

Icarus,

I'm new to this forum and not familiar with this button. I'll use it next time around.

Title: Re: Pseudoprimes
Post by BenVitale on Feb 20^th, 2008, 8:08pm

Can we argue that if we can solve the Discrete Log Problem very quickly, then we can can also factorize integers very quickly ?

Title: Re: Pseudoprimes
Post by Eigenray on Feb 20^th, 2008, 9:21pm

In fact we only need to solve the following problem: Given A, relatively prime to N, find a positive integer d such that A^d = 1 mod N. [For Carmichael numbers, this is trivial: take d=N-1.]

Suppose we want to factor N. We can assume N is odd and not a prime power (this can be checked quickly), so (http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/bbz.gif/N)^* is not cyclic. Pick A at random, and find d. Dividing by 2 if necessary, we can assume A^d/2 http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/ne.gif 1 mod N (d will be even with probability at least 3/4). Then the argument used [link=http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?action=display;board=riddles_putnam;num=1180641167;start=0#7]here[/link] works to show gcd(N, A^d/2-1) gives a non-trivial factor with probability at least 1/2.

Title: Re: Pseudoprimes
Post by BenVitale on Feb 20^th, 2008, 9:26pm

Eigenray,

I wrote, "... which means we can factor n/r using the Pollard rho factoring method with a very fast iterating function."
To that statement, you asked, "Why?"
..................................................
There's a good reason for that. And the reason is the Pollard rho factoring method

Here's a description of the Pollard rho factoring method : (see my next post)

Title: Re: Pseudoprimes
Post by Eigenray on Feb 20^th, 2008, 9:39pm

My 'Why?' was in reference to:

on 02/20/08 at 14:05:06, BenVitale wrote:

every prime divisor p of n/r is such that q divides p-1, which means we can factor n/r using the Pollard rho factoring method with a very fast iterating function.

Is there any particular reason why all the prime divisors being 1 mod q would make a number easier to factor via Pollard rho?

Title: Re: Pseudoprimes
Post by BenVitale on Feb 21^st, 2008, 3:19am

I will have to edit my last post "Pollard rho factoring method" as some of the tables got sqeezed in and some notations didn't turn out right.

I shall answer tomorrow to your question, as it is late and I'm ready to go to bed.

Title: Re: Pseudoprimes
Post by BenVitale on Feb 21^st, 2008, 12:11pm

Eigenray,

To the question, "Is there any particular reason why all the prime divisors being 1 mod q would make a number easier to factor via Pollard rho?"

I'll put the edited version, and an addition, I'll put up the next part of the description to getting why this is in my next post, however to state the answer bluntly, it's because if we know that p=1(modq), then the iterating function x^(2q) +1 will take approximately sqrt(p/2q) iterations to find the unknown prime p instead of sqrt(p) operations.

Title: Re: Pseudoprimes
Post by BenVitale on Feb 23^rd, 2008, 4:21am

Eigenray,

since you asked about why it was we could use a fast iterating function when p=1(mod q), im posting the following link
http://wwwmaths.anu.edu.au/~brent/pd/rpb061.pdf

Title: Re: Pseudoprimes
Post by BenVitale on Feb 23^rd, 2008, 4:47am

How to prove

Suppose we have integers N, A and X, such that A^X=1(modN), (A, N)=1, and N is squarefree.
If q^j is the largest prime power such that q^j | X, and A^X/q =/= 1(modN),
then every prime factor p_i of N/gcd(AX/q -1,N) is such that q^j | p_i -1.

Title: Re: Pseudoprimes
Post by Eigenray on Feb 23^rd, 2008, 12:44pm

on 02/23/08 at 04:21:26, BenVitale wrote:

Eigenray,
since you asked about why it was we could use a fast iterating function when p=1(mod q), im posting the following link
http://wwwmaths.anu.edu.au/~brent/pd/rpb061.pdf

Thanks. Of course: if m|p-1, then f(x)=x^m+1 mod p only takes on (p-1)/m non-zero values, so we'd expect a cycle within ~ http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/surd.gif{p/m} iterations.

However, apparently this simple heuristic is flawed when m=2, and http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/surd.gif{p/(m-1)} is closer.

on 02/23/08 at 04:47:25, BenVitale wrote:

Suppose we have integers N, A and X, such that A^X=1(modN), (A, N)=1, and N is squarefree.
If q^j is the largest prime power such that q^j | X, and A^X/q =/= 1(modN),
then every prime factor p_i of N/gcd(AX/q -1,N) is such that q^j | p_i -1.

It is similar to the proof for j=1. Let B = A^{X/q^j}. What is the order of B mod p?

Title: Re: Pseudoprimes
Post by BenVitale on Feb 24^th, 2008, 11:07pm

Eigenray,

Could you please explain?

If m=2, then Sqrt.{p/(m-1)} = sqrt(p) which is certainly not smaller than sqrt(p\2).

Title: Re: Pseudoprimes
Post by Eigenray on Feb 25^th, 2008, 8:26pm

I'm referring to the following paragraph from the linked article:

A more obvious conjecture replaces our http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/surd.gif{m-1} by http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/surd.gifm; this results from the idea that the recurrence relation corresponding to g(x) = x^m+1 (mod p) operates on a set of (p-1)/m residues when p=1 (mod m). The difference is important when m=2, as in the standard form of Brent's and Pollard's algorithms. The empirical results of Brent [1] (for m=2 and all odd primes p < 10⁸) and Table 1 discredit this conjecture.

Title: Re: Pseudoprimes
Post by BenVitale on Feb 27^th, 2008, 8:08pm

That is interesting! I've tried to figure it out since.
Could you explain why this is ?

Title: Re: Pseudoprimes
Post by BenVitale on Mar 24^th, 2008, 8:59am

Have you noticed that if N is a carmichael then the number (N-1) and (N+1) will usually have one extremely huge prime factor, much bigger than the rest?

For example,

Let N be the Carmichael numbers, i.e. 561, 1105, 1729, 2465, 2821, 6601, 8911, ...
Let N' be (N-1), i.e. 560, 1104, 1728, 2464, 2820, 6600, 8910, ...
Let N" be (N+1), i.e. 562, 1106, 1730, 2466, 2822, 6602, 8912, ...
N' and N" are the immediate neighbors of the Carmichael number N.

N':
----
560 : The prime factors are: 2 x 2 x 2 x 2 x 5 x 7
1104 : The prime factors are: 2 x 2 x 2 x 2 x 3 x 23
1728 : The prime factors are: 2 x 2 x 2 x 2 x 2 x 2 x 3 x 3 x 3
2464 : The prime factors are: 2 x 2 x 2 x 2 x 2 x 7 x 11
2820 : The prime factors are: 2 x 2 x 3 x 5 x 47
6600 : The prime factors are: 2 x 2 x 2 x 3 x 5 x 5 x 11
8910 : The prime factors are: 2 x 3 x 3 x 3 x 3 x 5 x 11

N" :
----
562 : The prime factors are: 2 x 281
1106 : The prime factors are: 2 x 7 x 79
1730 : The prime factors are: 2 x 5 x 173
2466 : The prime factors are: 2 x 3 x 3 x 137
2822 : The prime factors are: 2 x 17 x 83
6602 : The prime factors are: 2 x 3301
8912 : The prime factors are: 2 x 2 x 2 x 2 x 557

N" (=N+1) will usually have one extremely huge prime factor which is much bigger than the rest.

I went thru all the Carmichael numbers up to 825,266 : The prime factors are: 2 x 13 x 31741.

I find this curious. If Carmichael numbers were easy to generate, then one could use this to generate some very large prime numbers. However, Carmichael numbers are tougher to generate than the prime numbers.I can understand why at least N' would have to have some small prime divisors since lcm(p1-1,p2-...pn-1) divides N' where p1,p2,...,pn are the prime divisors of N.
Thus any small divisors of pk-1 for any k will also be a small divisor of N' as well.

Is this SIGNIFICANT enough?