Author |
Topic: Pseudoprimes (Read 3535 times) |
|
Benny
Uberpuzzler
Gender: 
Posts: 1024
|
 |
Pseudoprimes
« on: Feb 18th, 2008, 2:15pm » |
 Quote  Modify
|
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?
|
|
 IP Logged |
If we want to understand our world — or how to change it — we must first understand the rational choices that shape it.
|
|
|
Benny
Uberpuzzler
Gender:
Posts: 1024
|
|
Re: Pseudoprimes
« Reply #1 on: Feb 18th, 2008, 2:18pm » |
Quote Modify
|
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?
|
|
IP Logged |
If we want to understand our world — or how to change it — we must first understand the rational choices that shape it.
|
|
|
Eigenray
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 1948
|
|
Re: Pseudoprimes
« Reply #2 on: Feb 19th, 2008, 12:47pm » |
Quote Modify
|
on Feb 18th, 2008, 2:18pm, BenVitale wrote: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. |
|
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, A80 = 1 mod N for all A relatively prime to N. Then you wouldn't get any non-trivial factors.
Recall the Miller-Rabin test: write N-1 = 2sd, pick a random A, and if Ad  1 mod N, and A2^r d -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 AN-1 1 mod N, then N is not Carmichael. On the other hand, if AN-1 = 1 mod N, consider the smallest r for which A2^(r+1) d = 1 mod N. Then r  s-1, since AN-1=1 mod N, and r  0, since Ad 1 mod N. So we must have x = A2^r d  1 mod N, but x2 = 1 mod N. Then N divides neither x+1 nor x-1, while N | x2-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.
This thread is related: 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.
|
|
IP Logged |
|
|
|
Benny
Uberpuzzler
Gender:
Posts: 1024
|
|
Re: Pseudoprimes
« Reply #3 on: Feb 20th, 2008, 2:05pm » |
Quote Modify
|
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.
|
|
IP Logged |
If we want to understand our world — or how to change it — we must first understand the rational choices that shape it.
|
|
|
Benny
Uberpuzzler
Gender:
Posts: 1024
|
|
Re: Pseudoprimes
« Reply #4 on: Feb 20th, 2008, 2:16pm » |
Quote Modify
|
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.
|
|
IP Logged |
If we want to understand our world — or how to change it — we must first understand the rational choices that shape it.
|
|
|
Eigenray
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 1948
|
|
Re: Pseudoprimes
« Reply #5 on: Feb 20th, 2008, 2:55pm » |
Quote Modify
|
on Feb 20th, 2008, 2:05pm, 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 Ax/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?
|
|
IP Logged |
|
|
|
Icarus
wu::riddles Moderator
Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863
|
|
Re: Pseudoprimes
« Reply #6 on: Feb 20th, 2008, 7:13pm » |
Quote Modify
|
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?
|
|
IP Logged |
"Pi goes on and on and on ...
And e is just as cursed.
I wonder: Which is larger
When their digits are reversed? " - Anonymous
|
|
|
Benny
Uberpuzzler
Gender:
Posts: 1024
|
|
Re: Pseudoprimes
« Reply #7 on: Feb 20th, 2008, 8:04pm » |
Quote Modify
|
Icarus,
I'm new to this forum and not familiar with this button. I'll use it next time around.
|
|
IP Logged |
If we want to understand our world — or how to change it — we must first understand the rational choices that shape it.
|
|
|
Benny
Uberpuzzler
Gender:
Posts: 1024
|
|
Re: Pseudoprimes
« Reply #8 on: Feb 20th, 2008, 8:08pm » |
Quote Modify
|
Can we argue that if we can solve the Discrete Log Problem very quickly, then we can can also factorize integers very quickly ?
|
|
IP Logged |
If we want to understand our world — or how to change it — we must first understand the rational choices that shape it.
|
|
|
Eigenray
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 1948
|
|
Re: Pseudoprimes
« Reply #9 on: Feb 20th, 2008, 9:21pm » |
Quote Modify
|
In fact we only need to solve the following problem: Given A, relatively prime to N, find a positive integer d such that Ad = 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 ( /N)* is not cyclic. Pick A at random, and find d. Dividing by 2 if necessary, we can assume Ad/2 1 mod N (d will be even with probability at least 3/4). Then the argument used here works to show gcd(N, Ad/2-1) gives a non-trivial factor with probability at least 1/2.
|
| « Last Edit: Feb 20th, 2008, 9:29pm by Eigenray » |
IP Logged |
|
|
|
Benny
Uberpuzzler
Gender:
Posts: 1024
|
|
Re: Pseudoprimes
« Reply #10 on: Feb 20th, 2008, 9:26pm » |
Quote Modify
|
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)
|
|
IP Logged |
If we want to understand our world — or how to change it — we must first understand the rational choices that shape it.
|
|
|
Eigenray
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 1948
|
|
Re: Pseudoprimes
« Reply #11 on: Feb 20th, 2008, 9:39pm » |
Quote Modify
|
My 'Why?' was in reference to:
on Feb 20th, 2008, 2:05pm, 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?
|
| « Last Edit: Feb 20th, 2008, 9:40pm by Eigenray » |
IP Logged |
|
|
|
Benny
Uberpuzzler
Gender:
Posts: 1024
|
|
Re: Pseudoprimes
« Reply #12 on: Feb 21st, 2008, 3:19am » |
Quote Modify
|
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.
|
|
IP Logged |
If we want to understand our world — or how to change it — we must first understand the rational choices that shape it.
|
|
|
Benny
Uberpuzzler
Gender:
Posts: 1024
|
|
Re: Pseudoprimes
« Reply #13 on: Feb 21st, 2008, 12:11pm » |
Quote Modify
|
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.
|
|
IP Logged |
If we want to understand our world — or how to change it — we must first understand the rational choices that shape it.
|
|
|
Benny
Uberpuzzler
Gender:
Posts: 1024
|
|
Re: Pseudoprimes
« Reply #14 on: Feb 23rd, 2008, 4:21am » |
Quote Modify
|
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
|
|
IP Logged |
If we want to understand our world — or how to change it — we must first understand the rational choices that shape it.
|
|
|
Benny
Uberpuzzler
Gender:
Posts: 1024
|
|
Re: Pseudoprimes
« Reply #15 on: Feb 23rd, 2008, 4:47am » |
Quote Modify
|
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.
|
|
IP Logged |
If we want to understand our world — or how to change it — we must first understand the rational choices that shape it.
|
|
|
Eigenray
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 1948
|
|
Re: Pseudoprimes
« Reply #16 on: Feb 23rd, 2008, 12:44pm » |
Quote Modify
|
on Feb 23rd, 2008, 4:21am, BenVitale wrote:
Thanks. Of course: if m|p-1, then f(x)=xm+1 mod p only takes on (p-1)/m non-zero values, so we'd expect a cycle within ~  {p/m} iterations.
However, apparently this simple heuristic is flawed when m=2, and {p/(m-1)} is closer.
on Feb 23rd, 2008, 4:47am, 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 = AX/q^j. What is the order of B mod p?
|
|
IP Logged |
|
|
|
Benny
Uberpuzzler
Gender:
Posts: 1024
|
|
Re: Pseudoprimes
« Reply #17 on: Feb 24th, 2008, 11:07pm » |
Quote Modify
|
Eigenray,
Could you please explain?
If m=2, then Sqrt.{p/(m-1)} = sqrt(p) which is certainly not smaller than sqrt(p\2).
|
|
IP Logged |
If we want to understand our world — or how to change it — we must first understand the rational choices that shape it.
|
|
|
Eigenray
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 1948
|
|
Re: Pseudoprimes
« Reply #18 on: Feb 25th, 2008, 8:26pm » |
Quote Modify
|
I'm referring to the following paragraph from the linked article:
A more obvious conjecture replaces our {m-1} by m; this results from the idea that the recurrence relation corresponding to g(x) = xm+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 < 108) and Table 1 discredit this conjecture.
|
|
IP Logged |
|
|
|
Benny
Uberpuzzler
Gender:
Posts: 1024
|
|
Re: Pseudoprimes
« Reply #19 on: Feb 27th, 2008, 8:08pm » |
Quote Modify
|
That is interesting! I've tried to figure it out since.
Could you explain why this is ?
|
|
IP Logged |
If we want to understand our world — or how to change it — we must first understand the rational choices that shape it.
|
|
|
Benny
Uberpuzzler
Gender:
Posts: 1024
|
|
Re: Pseudoprimes
« Reply #20 on: Mar 24th, 2008, 8:59am » |
Quote Modify
|
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?
|
|
IP Logged |
If we want to understand our world — or how to change it — we must first understand the rational choices that shape it.
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print