From: robert maas, see http://tinyurl.com/uh3t
Subject: Seeking efficient sequential-Carmichael-number generator
Date:
Message-ID: <rem-2007jan17-001@yahoo.com>
I generated a tiny initial segment of the following sequence:
Carmichael numbers that have smallest prime factor larger than that
of any smaller Carmichael number, as follows:
First I copied the very small list of consecutive Carmichael
numbers that I could find online
<http://www.research.att.com/~njas/sequences/A002997>
then built an enumeration of consecutive Carmichael numbers that
simply exhausts that list then signals an error, then filtered that
enumeration in the following way:
(setq prevfac1 1)
(setq cnen (init-carmichael-numbers)) ;Init an enumeration of C.numbers
(prog () lp
(setq cn (next-carmichael-number cnen)) ;Step enumeration to get next C.number
(if (setq p1 (q1f cn 3 prevfac1)) (go lp))
(setq p1 (q1f cn (max 3 prevfac1) cn))
(format t " ~D(~D) " cn p1) (finish-output)
(setq prevfac1 p1) (go lp)
)
Output was:
561(3) 1105(5) 1729(7) 29341(13) 162401(17) 252601(41)
So then I stripped off the factors and formatted the sequence as:
561,1105,1729,29341,162401,252601
and tried to search for it, getting:
I am sorry, but the terms do not match anything in the table.
If your sequence is of general interest, please send it to me using
the form provided and I will (probably) add it to the data base!
Include a brief description and if possible enough terms to fill 3
lines on the screen. I need a minimum of 4 terms.
I do have six terms, which is more than the bare minimum of four,
but I'd prefer to get a few more terms, 3 lines full if possible.
Does anybody know of a good algorithm for efficiently generating
all the Carmichael numbers in sequence, so that I might replace my
hack canned-list enumeration with something decent, and then apply
my larger-smallest-prime-factor filter on that sequence to produce
more terms of my sequence?
Why is this sequence useful? For testing factoring algorithms,
where you want the smallest factor as large as possible to more
severely test the algorithm, but you want the actual number to
factor to be as small as possible so you aren't just wasting time
factoring a large number when a smaller number would have tested
the algorithm just as well, and of course you want to restrict the
numbers to Carmichael numbers for one set of test data.
(The other three sets are:
- true primes, which the algorithm should recognize as primes and
not waste effort trying to factor,
- regular composites, which immediately show themselves as
composite via Fermat's test nearly 100% of the time,
- semi-pseudoprimes which pass Fermat's test only some
intermediate fraction of the time, so they fall on a continuum
between regular composites and Carmichael numbers;
The full test set would be a random mix of the four kinds of
numbers.)
My sequence represents all "best" points of this partial ordering
(cost vs. benefit tradeoff) for the Carmichael number portion of
the test set.
A program for making Carmichael numbers in source code format:
http://aminet.net/package/dev/src/Carmichael
More Carmichael number stuff:
http://primes.utm.edu/glossary/page.php?sort=CarmichaelNumber
http://www.chalcedon.demon.co.uk/rgep/carpsp.html
http://www.ams.org/mcom/1996-65-214/S0025-5718-96-00692-8/S0025-5718-96-00692-8.pdf
http://www.chalcedon.demon.co.uk/rgep/p78pa1.pdf
http://rooster.stanford.edu/~ben/maths/numbertheory/carmichael.html
Etc.
This will produce plenty more:
http://www.google.com/search?q=%22carmichael+numbers%22&hl=en&lr=&start=10&sa=N
From: robert maas, see http://tinyurl.com/uh3t
Subject: Re: Seeking efficient sequential-Carmichael-number generator
Date:
Message-ID: <rem-2007jan18-006@yahoo.com>
> From: "user923005" <·······@connx.com>
> A program for making Carmichael numbers in source code format:
> http://aminet.net/package/dev/src/Carmichael
Download: http://aminet.net/dev/src/Carmichael.lha - View contents
Well I downloaded it, got a gz file, ungzipped it, now have:
4 -rw------- 1 rem user 2835 Jan 18 20:09 Carmichael.lha
which starts like this:
···········@·@<BE>···@·@<D4><A6>·····@^XCarmichael\Anleitung.txtI^U^B^Ec<97><AD>
<B6><A4><9C><EF><C0>^_<F2>^BV2<DC>,^A^PdSm<83>%<81> Q^Y#<8D><D9>^?$<FA>ESCr
<A6><FE><ED>^U<F1>@<F0>#p}<C8>m<B1>m<C0>^G9<C4>^^]<D6>6<93><CA><F6><89>^\<9F>`l
<90>q<B2>^N*<AD>`<B5>y<B8><FD><C1><F2>^XD<AE>xp/^Z<BD>?<FF><94><AD><F4>:^C<94>
<9E>^Y<AA><B4>\!<F0><85><D6>A<8E>rZ<DC>^Ye]d<FD>^B<F0><D4><96>><D9>j>l<B5><A2>
<F5><AB><F3><C4>^QH<F0><C3><CF>^Ph! <CE><F3>^L^\<C3><A3><E2>10<EA><CE>0iD
<E7><<AC><B2>;<A1>H^G<BE><E4><80>xt<B1><A6>0V<BD>z<D3><8C>^B<D3>=4<F8><BC>I<EC>
<B7><DF>^AA=;<D9>Q<96><A1>]W9CC<98>M<A4>5<DF>0<F7><FA><A2>r<D0>K'<D7>8<F3>/<A2>
So how do I convert it to anything legible?
On Fri, 19 Jan 2007 05:17:48 +0100, robert maas, see
http://tinyurl.com/uh3t <·······@yahoo.com> wrote:
>> From: "user923005" <·······@connx.com>
>> A program for making Carmichael numbers in source code format:
>> http://aminet.net/package/dev/src/Carmichael
> Download: http://aminet.net/dev/src/Carmichael.lha - View contents
>
> Well I downloaded it, got a gz file, ungzipped it, now have:
> 4 -rw------- 1 rem user 2835 Jan 18 20:09 Carmichael.lha
> which starts like this:
> ···········@·@<BE>···@·@<D4><A6>·····@^XCarmichael\Anleitung.txtI^U^B^Ec<97><AD>
> <B6><A4><9C><EF><C0>^_<F2>^BV2<DC>,^A^PdSm<83>%<81>
> Q^Y#<8D><D9>^?$<FA>ESCr
> <A6><FE><ED>^U<F1>@<F0>#p}<C8>m<B1>m<C0>^G9<C4>^^]<D6>6<93><CA><F6><89>^\<9F>`l
> <90>q<B2>^N*<AD>`<B5>y<B8><FD><C1><F2>^XD<AE>xp/^Z<BD>?<FF><94><AD><F4>:^C<94>
> <9E>^Y<AA><B4>\!<F0><85><D6>A<8E>rZ<DC>^Ye]d<FD>^B<F0><D4><96>><D9>j>l<B5><A2>
> <F5><AB><F3><C4>^QH<F0><C3><CF>^Ph!
> <CE><F3>^L^\<C3><A3><E2>10<EA><CE>0iD
> <E7><<AC><B2>;<A1>H^G<BE><E4><80>xt<B1><A6>0V<BD>z<D3><8C>^B<D3>=4<F8><BC>I<EC>
> <B7><DF>^AA=;<D9>Q<96><A1>]W9CC<98>M<A4>5<DF>0<F7><FA><A2>r<D0>K'<D7>8<F3>/<A2>
> So how do I convert it to anything legible?
http://en.wikipedia.org/wiki/LHA_(file_format)
--
Using Opera's revolutionary e-mail client: http://www.opera.com/mail/
On Fri, 19 Jan 2007 06:16:54 +0100, John Thingstad
<··············@chello.no> wrote:
http://izarc.org/download/IZArc_Setup.exe
did it for me
--
Using Opera's revolutionary e-mail client: http://www.opera.com/mail/
In comp.lang.lisp robert maas, see http://tinyurl.com/uh3t <·······@yahoo.com> wrote:
> > From: "user923005" <·······@connx.com>
> > A program for making Carmichael numbers in source code format:
> > http://aminet.net/package/dev/src/Carmichael
> Download: http://aminet.net/dev/src/Carmichael.lha - View contents
>
> Well I downloaded it, got a gz file, ungzipped it, now have:
> 4 -rw------- 1 rem user 2835 Jan 18 20:09 Carmichael.lha
> which starts like this:
<skipped binary junk>
Do not bother unpacking this archive. The programs is just a
naive double loop (will take hours to get up to 100000000), you
can easily write a better one.
--
Waldek Hebisch
·······@math.uni.wroc.pl
From: robert maas, see http://tinyurl.com/uh3t
Subject: Re: Seeking efficient sequential-Carmichael-number generator
Date:
Message-ID: <rem-2007jan19-001@yahoo.com>
(After my nap, more response:)
> From: "user923005" <·······@connx.com>
> More Carmichael number stuff:
> http://primes.utm.edu/glossary/page.php?sort=CarmichaelNumber
The composite integer n is a Carmichael number if a^n-1=1 (mod n) for
every integer a relatively prime to n. (This condition is satisfied by
all primes because of Fermat's Little Theorem.) The Fermat probable
primality test will fail to show a Carmichael number is composite
until we run across one of its factors!
Yeah, but the Fermat-Maas test will pop out not just proof of
non-primeness but an actual partial factorization, usually on the
very first base (2) that it tries. So what's the big deal about
these masquerading as primes if it's so easy to crack them wide
open? They're even less secure than ordinary composite numbers that
violate Fermat's test but give you no clue how to factor them.
Related pages (outside of this work)
* The Carmichael's to 10^16
-> <http://primes.utm.edu/glossary/page.php?sort=CarmichaelNumber>
(Rearraged by me to organize my reply better:)
* even-12 The 155 even pseudoprimes up to 10^12.
(Who the fuck cares? As if a even number, low order digit
0,2,4,6,8, will fool anyone into thinking it's really prime??
What is this, "Pseudo Primes for DUMMIES"?)
161038 2 73 1103
(exptmod 2 161037 161038) = 80520
It doesn't even pass Fermat's test for base=2. In what sense does
anybody think this is a pseudo-prime?
* spsp-13.gz The 58892 strong (Miller--Rabin) pseudoprimes up to
10^13 in GZIP format
I looked seriously at this file first, since some people are
bragging about how the Miller--Rabin test is so wonderful, that it
catches non-primes that the Fermat test thinks are prime. So let's
try the Fermat-Maas test on some of these:
The very last one (the largest) in the list:
(setq p 9998974546471)
(setq pm1facs (qf (+ -1 p) 10000))
;(2 3 3 3 5 7 7 7 13 37 224467)
(prove-prime-or-not p pm1facs :trace t)
p=9998974546471? #7<2>---#4<3>-#3<5> xx
Falls rapidly to Fermat-Maas test.
(exptmod 5 9998974546470 9998974546471) = 4210093057313 .neq. 1
That's why!
Well, that's enough of that! Next I switched over to:
* psp-12.gz The 101629 pseudoprimes up to 10^12 in GZIP format
341 11 31
In what sense is that a "pseudoprime"?? Oh, if you use base=2 or 3,
it passes Fermat test, but it fails as soon as you try base=5.
Oh, and also this:
Error in function SPEW-FAJJAL-TESTS: composite x=341=(11 31) tests as prime
You remember when Fajjal proposed a simple formula that he claimed
would detect primes x greater than fixed prime p, but for p=2, x=341 failed?
Bit of trivia, two of the Carmichael numbers geerated&posted by Marc Bogaerts:
852841 = 2501 * 341
2100901 = 6161 * 341
Now to really check out these alleged pseudoprimes. The real test
is not whether the first few possible bases in sequence are Fermat
liars, but what the fraction of liars there are overall.
(diagnose-pseudoprime 341)
49/149 = 0.32885906 (out of relatively-prime bases)
49/169 = 0.28994083 (out of *all* bases in [2,p-2])
Less than 30% chance random Fermat test will fail.
That's not impressive at all. And even on the rare chance it succeeds:
(exptmod 311 340 341) = 1
you can simply switch to the full Fermat-Maas test:
(setq pm1facs (qf (+ -1 (setq p 341)) 20)) ;(2 2 5 17)
(prove-prime-or-not p pm1facs :trace t)
p=341? #3<2>
** Found 32**2 =modp= 1, hence p=341 not prime!
xxxx
p = 11 * 31
Next entry in the list, the first Carmichael number, whose decimal
representation I almost have memorized now.
561 3 11 17
(diagnose-pseudoprime 561)
:CARMICHAEL (i.e. 100% of rel.prime bases)
53/93 = 0.56989247 (out of *all* bases in [2,p-2])
Now we run all the way to the end:
999986341201 17 41 43 331 100801
It would take too long to count *all* the times Fermat fails out of
the total interval [2,999986341199], so I'll just do a quick random
sample:
(setq res (list)) (dotimes (i 10 res) (push (likely-prime 999986341201) res))
(NIL NIL NIL NIL NIL NIL NIL NIL NIL NIL)
Not even one out of ten Fermat liars. Some more samples:
(NIL NIL NIL NIL T NIL NIL NIL T NIL)
(NIL NIL NIL NIL NIL NIL T NIL NIL NIL)
(NIL NIL NIL NIL NIL NIL NIL NIL T NIL)
OK, so it does like some small fraction of the time.
(setq pm1facs (qf (+ -1 (setq p 999986341201)) 20))
;(2 2 2 2 3 5 5 7 11 10822363)
(prove-prime-or-not p pm1facs :trace t)
p=999986341201? #6<2>
** Found 294113629766**2 =modp= 1, hence p=999986341201 not prime!
xxxx
p = 17 * 58822725953
Any pseudoprime of the form 4*k+1 is likely to fall to that
too-many-square-roots-of-1 detector I added a few days ago.
Let's see if I can find one of the form 4*k+3 which won't be so
easy to crack:
999828475651 191 4751 1101811
(setq res (list)) (dotimes (i 40 res) (push (likely-prime 999828475651) res))
(NIL NIL NIL NIL NIL NIL NIL NIL NIL NIL NIL NIL NIL NIL NIL NIL NIL NIL NIL
NIL NIL NIL NIL NIL NIL NIL NIL NIL NIL NIL NIL NIL NIL NIL NIL NIL NIL NIL
NIL NIL)
That's not a decent pseudoprime at all, if you pick random bases.
(setq pm1facs (qf (+ -1 (setq p 999828475651)) 20))
;(2 3 3 5 5 19 116939003)
(prove-prime-or-not p pm1facs :trace t)
p=999828475651? #5<2>
** Found 633312148311**2 =modp= 1, hence p=999828475651 not prime!
xxxx
p = 1101811 * 907441
Cruddy pseudoprime falls to Fermat-Maas test once again!
Let's try one that doesn't have any small factors:
999647922737 816353 1224529
(setq p 999647922737)
(setq pm1facs (qf (+ -1 p) 10000))
;(2 2 2 2 97 263 2449061)
(prove-prime-or-not p pm1facs :trace t)
p=999647922737? #4<2>
** Found 4898117**2 =modp= 1, hence p=999647922737 not prime!
xxxx
p = 816353 * 1224529
At that point I decided to write a special function that did *only*
the check for too many square roots. But it'd detect too many
square roots of *any* number, not just too many square roots of 1.
So after my nap I wrote it, and tried it on a few cases. Most
worked fine, but one screwed up. I tracked down the bug and fixed
it, so now the problem case gives:
999746703869 408197 2449177
(setq p 999746703869)
(setq pm1facs (qf (+ -1 p) 10000))
;(2 2 11 19 41 53 131 4201)
(prove-prime-or-not p pm1facs :trace t)
p=999746703869? #7<2>----#3<3> xx
(pm1facs-find-multi-sqrts pm1facs)
Oh Oh. First time I tried this case it screwed up. I found the bug and
fixed it. Now it works correctly, detecting (and distinguishing) when
it first runs into p-1 whose square is already known to be 1, and the
first time it finds two numbers with the same square but *not*
additive inverses (a+b=p) whereby (a-b)*(a+b) gives nontrivial partial
factorization of p. Here's the correct output now:
* prevpwr=544788489860 --new-> thispwr=999746703868=p-1 --already-known-> 1
(at base=2)
** Found 857889266036 = 258041733551**2 = 941653331421**2 (mod p),
hence p=999746703869 not prime! (at base=5)
** 999746703869 = 408197 * 2449177
What happened previously was that it wouldn't notice p-1-->p was
already known, so it'd enter a second copy of it, then notice there
are now two copies and since the sum (of the two identical values p-1)
isn't exactly p, you can guess the rest...
So I wrote the code from scratch after my nap, it had one bug, fixed
the bug before bedtime, and I think it might possibly be bug-free now.
Let me go to the other file and get some more test data ...
So now let's go back to all the cases where I used the Fermat-Maas
test but it actually found a extra sqrt(1), and try those same
cases with the new too-many-sqrts-only test:
(setq pm1facs (qf (+ -1 (setq p 9998974546471)) 10000))
;(2 3 3 3 5 7 7 7 13 37 224467)
(pm1facs-find-multi-sqrts pm1facs)
** Found 1 = 4210093057313**2 = 9998974546470**2 (mod p),
hence p=9998974546471 not prime! (at base=5)
** 9998974546471 = 14141401 * 707071
(setq pm1facs (qf (+ -1 (setq p 341)) 20))
;(2 2 5 17)
(pm1facs-find-multi-sqrts pm1facs)
** Found 1 = 32**2 = 340**2 (mod p), hence p=341 not prime! (at base=2)
** 341 = 11 * 31
(setq pm1facs (qf (+ -1 (setq p 999986341201)) 20))
;(2 2 2 2 3 5 5 7 11 10822363)
(pm1facs-find-multi-sqrts pm1facs)
** Found 1 = 294113629766**2 = 999986341200**2 (mod p),
hence p=999986341201 not prime! (at base=2)
** 999986341201 = 17 * 58822725953
(setq pm1facs (qf (+ -1 (setq p 999828475651)) 20))
;(2 3 3 5 5 19 116939003)
(pm1facs-find-multi-sqrts pm1facs)
** Found 1 = 633312148311**2 = 999828475650**2 (mod p),
hence p=999828475651 not prime! (at base=2)
** 999828475651 = 1101811 * 907441
(setq pm1facs (qf (+ -1 (setq p 999647922737)) 10000))
;(2 2 2 2 97 263 2449061)
(pm1facs-find-multi-sqrts pm1facs)
** Found 1 = 4898117**2 = 999647922736**2 (mod p),
hence p=999647922737 not prime! (at base=2)
** 999647922737 = 816353 * 1224529
OK, let's try that last file:
* psp13.gz The 162610 pseudoprimes between 10^12 and 10^13 in GZIP
format
1357915997593 1042273 1302841
(setq res (list)) (dotimes (i 40 res) (push (likely-prime 1357915997593) res))
(NIL NIL NIL NIL NIL T NIL NIL NIL NIL NIL NIL NIL T NIL NIL NIL NIL NIL NIL
NIL NIL NIL NIL NIL NIL NIL NIL NIL NIL NIL NIL NIL NIL NIL NIL NIL NIL NIL
NIL)
It's a joke! Only 2 out of 40 random bases fooled Fermat test!
(setq pm1facs (qf (+ -1 (setq p 1357915997593)) 20))
;(2 2 2 3 3 3 3 7 11 27214927)
(prove-prime-or-not p pm1facs :trace t)
p=1357915997593? #5<2>
** Found 10422729**2 =modp= 1, hence p=1357915997593 not prime!
xxxx
p = 1042273 * 1302841
(pm1facs-find-multi-sqrts pm1facs)
** Found 1 = 10422729**2 = 1357915997592**2 (mod p),
hence p=1357915997593 not prime! (at base=2)
** 1357915997593 = 1042273 * 1302841
It's a double joke! So fucking easy to factor it by too-many-sqrts test.
Do you know of *any* actually difficult-to-detect pseudoprimes, where:
- A large *majority* of random bases are Fermat liars.
- The number itself doesn't have any small factors that would yield
to brute-force trial division.
- No two powers of any small base have the same square that would
quickly yield to too-many-sqrts test.
In comp.lang.lisp robert maas, see http://tinyurl.com/uh3t <·······@yahoo.com> wrote:
> * even-12 The 155 even pseudoprimes up to 10^12.
> (Who the fuck cares? As if a even number, low order digit
> 0,2,4,6,8, will fool anyone into thinking it's really prime??
> What is this, "Pseudo Primes for DUMMIES"?)
> 161038 2 73 1103
> (exptmod 2 161037 161038) = 80520
> It doesn't even pass Fermat's test for base=2. In what sense does
> anybody think this is a pseudo-prime?
>
(exptmod 2 161038 161038) = 2
You and I do not care about them, but Pinch wanted to show off that
his method can find such numbers, so do not spoil the fun.
> * spsp-13.gz The 58892 strong (Miller--Rabin) pseudoprimes up to
> 10^13 in GZIP format
> I looked seriously at this file first, since some people are
> bragging about how the Miller--Rabin test is so wonderful, that it
> catches non-primes that the Fermat test thinks are prime. So let's
> try the Fermat-Maas test on some of these:
>
Robert, did you read the text carfully: those are composite numbers that
pass Miller-Rabin test using just one base (namely 2). This is an
extremaly lame version of Miller-Rabin test, and still false positive
are quite rare.
I think you did not understand role of Pinch list (and similar lists):
checking all numbers on Pinch list you can find all bad cases for
Miller-Rabin which up to 10^13. Jaeschke checked numbers up to
341,550,071,728,321 (I do not know how), and the list of "bad cases"
for Miller-Rabin is:
25326001, 161304001, 960946321, 1157839381, 3697278427, 5764643587,
6770862367, 14386156093, 15579919981, 18459366157, 19887974881,
21276028621, 3215031751, 118670087467, 128282461501, 354864744877,
546348519181, 602248359169, 669094855201, 2152302898747, 3474749660383
Note, that (if you belive Jaeschke) for numbers smaller than
341,550,071,728,321 it is enough to run Miller-Rabin with
base 2, 3, 5, 7, 11, 13, and 17. The list of bad cases is used
for numbers smaller than 10^13 to skip most of the tests (it is
faster to test if a number is on "bad" list, than to run extra
test).
> At that point I decided to write a special function that did *only*
> the check for too many square roots. But it'd detect too many
> square roots of *any* number, not just too many square roots of 1.
>
FYI, such test is a well-known improvement to Miller-Rabin test. One
possible example is:
1377161253229053 * 413148375987157
> Do you know of *any* actually difficult-to-detect pseudoprimes, where:
> - A large *majority* of random bases are Fermat liars.
Theorem: n is either Carmichael or there is at most 50% Fermat liars
> - The number itself doesn't have any small factors that would yield
> to brute-force trial division.
> - No two powers of any small base have the same square that would
> quickly yield to too-many-sqrts test.
AFAICS you get too many sqrts if small numbers generate the whole
Z/(nZ) group. Wikipedia:
http://en.wikipedia.org/wiki/Miller-Rabin_primality_test
claims that if GRH is true than it is enough to take
numbers up to 2*log(n)^2.
--
Waldek Hebisch
·······@math.uni.wroc.pl
From: robert maas, see http://tinyurl.com/uh3t
Subject: Re: Seeking efficient sequential-Carmichael-number generator
Date:
Message-ID: <rem-2007jan23-003@yahoo.com>
> From: Waldek Hebisch <·······@math.uni.wroc.pl>
> > * even-12 The 155 even pseudoprimes up to 10^12.
> > (Who the fuck cares? As if a even number, low order digit
> > 0,2,4,6,8, will fool anyone into thinking it's really prime??
> > What is this, "Pseudo Primes for DUMMIES"?)
> > 161038 2 73 1103
> > (exptmod 2 161037 161038) = 80520
> > It doesn't even pass Fermat's test for base=2. In what sense does
> > anybody think this is a pseudo-prime?
> > (exptmod 2 161038 161038) = 2
> You and I do not care about them, but Pinch wanted to show off that
> his method can find such numbers, so do not spoil the fun.
But in what sense are they pseudo-primes? The very first base usually
tested (if not a random base) is 2, where every even number fails.
What exactly is he showing off. That he can pick random even numbers??
> > * spsp-13.gz The 58892 strong (Miller--Rabin) pseudoprimes up to
> > 10^13 in GZIP format
> > I looked seriously at this file first, since some people are
> > bragging about how the Miller--Rabin test is so wonderful, that it
> > catches non-primes that the Fermat test thinks are prime. So let's
> > try the Fermat-Maas test on some of these:
> ... those are composite numbers that pass Miller-Rabin test using
> just one base (namely 2). This is an extremaly lame version of
> Miller-Rabin test, and still false positive are quite rare.
I presume it's been proven that there are an infinite number of
such numbers where that test lies, hence that test plus a finite
list of exceptions isn't sufficient in general? So I guess he's just
showing off these very few (less than 60k) of the infinite number?
Still I see no useful value, given that it's primes with more than
a hundred digits that somebody might want to certify for
cryptographic purposes, nothing with only 13 digits as he tests
there. Has anybody found any 100+ digit composites which nevertheless
pass various "strong" tests of primality?
By the way, a few days ago I wrote a program that looks for too
many square-roots of any residue whatsoever (modulo the number
being tested for primality), which goes beyond the check in my
Fermat-Maas test for too many square roots of 1 (1 and -1 are
square roots, any other square root immediately proves the modulus
isn't prime). Given a Carmichael number it very quickly finds an
extra square root of something, from which it promptly uses GCD to
generate a partial factorization of the modulus (the Carmichael
number).
Then yesterday I got curious whether the same trick would work with
other roots, such as cube roots or fifth roots etc., whenever p-1
is divisible by 3 or 5 etc. respectively. I did some playing around
and found indeed for a given modulus there are three kinds of roots:
- Where base**lowpower = 1, so it's of no use.
- Where base**lowpower not 1, so you get a nontrivial root, but
both gcds give 1, so you don't get a useful factorization.
- Where base**lowpower not 1, and at least one of the GCDs gives a
nontrivial factor.
For any given modulus, there were typically several factors of n-1
in each category, in particular in that last category where the
method works. Note I was considering only roots of 1 here, not
excess roots of other residues, because I was playing around by
hand where it's easy to see if 1 appears but harder to check for
duplicates in a growing list.
I'm thinking of generalizing all this to combine all prime factors
of n-1 and such roots of all residues not just 1. One nice thing
about this technique is that it doesn't require complete
factorization of n-1. It's sufficient to find several small prime
factors and try each of them for excess roots.
Hey, here's a challenge to Dik, and anyone else who claims to use a
really good test of primality. Tell me which of the following
numbers you can prove prime or not-prime, and how you proved each:
161017961707897257848197034095085883701658444628134743244626983732175127324625395109542778299825783938179011415448625509
207677323212653460189763715018168148562736912770165859554987863067225238037621465735062178016617530680500845611760610773
213437807628312594010808590405805687520168143511854996543485955020273779058360393464263881935702811899720655707865102949
243350802602353779525695575425605604497717590441278555518996915284614880077485881590341984414620628312935448230821480437
350846548354507714830992780248512830501450385743913897073481741686902214689848981403722865178992426159325990291343232893
384357716052617382919009473741089174454600459530915162221614905199783350232590494229887837440479410244951770847931870629
408734750590002753979833708941973459034269960365557817502727387911810507734203788675391614200042406273586117892305006277
424004627402149852205987601451365609253735347986132432847055788777032269305076297619976745149952328355028364877602092613
527090644479460762928592724265236091350107693154350627845068377808509964471886168529685941116785456988357309289753471869
549996561526162014742424498213829420624057396097607309775073116523396495711196859661029164016231837272699467905827719493
682053974682113303367535526029046876699183979938621104663400520442705973534950475666203428231326973988093279684398840197
815067983223607302820567450959009509553761213910988385519497060433420548941656235082042818461845050524222513615149104197
977607633328794837559063268598964146190076396068173382266865941373954922186961470556205311080943050833355378055893544773
More reply later...
In comp.lang.lisp robert maas, see http://tinyurl.com/uh3t <·······@yahoo.com> wrote:
> > From: Waldek Hebisch <·······@math.uni.wroc.pl>
> > > * even-12 The 155 even pseudoprimes up to 10^12.
> > > (Who the fuck cares? As if a even number, low order digit
> > > 0,2,4,6,8, will fool anyone into thinking it's really prime??
> > > What is this, "Pseudo Primes for DUMMIES"?)
> > > 161038 2 73 1103
> > > (exptmod 2 161037 161038) = 80520
> > > It doesn't even pass Fermat's test for base=2. In what sense does
> > > anybody think this is a pseudo-prime?
> > > (exptmod 2 161038 161038) = 2
> > You and I do not care about them, but Pinch wanted to show off that
> > his method can find such numbers, so do not spoil the fun.
>
> But in what sense are they pseudo-primes? The very first base usually
> tested (if not a random base) is 2, where every even number fails.
> What exactly is he showing off. That he can pick random even numbers??
>
Hmm, I wrote this above in Lisp notation. Again, Pinch says that a number
n is a pseudoprime iff 2^n = 2 mod n. Note that if n is odd you can
divide both sides by 2 to get more usual definition.
> I presume it's been proven that there are an infinite number of
> such numbers where that test lies, hence that test plus a finite
> list of exceptions isn't sufficient in general? So I guess he's just
> showing off these very few (less than 60k) of the infinite number?
> Still I see no useful value, given that it's primes with more than
> a hundred digits that somebody might want to certify for
> cryptographic purposes, nothing with only 13 digits as he tests
> there. Has anybody found any 100+ digit composites which nevertheless
> pass various "strong" tests of primality?
>
Well, single round of Rabin-Miller has probability of failure 1/4.
If you do many round the probability of failure gets very small.
So if you can find a large composite number which passes
Rabin-Miller test then something is wrong with math or (more likely)
you have defective random number generator. For cryptographic
purposes you _must_ belive in probability anyway, so I am
satified with say 500 rounds of Rabin-Miller.
OTOH as a matematician I want to do proof and provably correct
computations. I may need many primes, so I want to get them fast,
but I also want certainity. For such purpose I can re-use
Pinch result (note that directly checking 10^13 numbers for
primality is a large computation, while Pinch method checked number
up to 10^10 for simpler property).
Also, since Pinch found all pseudoprimes (with respect to base 2)
below 10^13 one can do some statistics and guess how bigger
number behave.
BTW. Pinch claims that he recently extended his tables up to
10^18, but I do not know if he made his bigger tables public.
> By the way, a few days ago I wrote a program that looks for too
> many square-roots of any residue whatsoever (modulo the number
> being tested for primality), which goes beyond the check in my
> Fermat-Maas test for too many square roots of 1 (1 and -1 are
> square roots, any other square root immediately proves the modulus
Hmm, this is Miller-Rabin. More precisely, if n-1 = 2^s * m and
m is odd then Miller-Rabin computes b = a^m and check if it is 1.
If yes then a passed one round. Otherwise repeatedly square b
trying to get 1. If you do not get 1 after s step then a failed
(in fact, a failed Fermat test). If you got 1 you check the
reslut of prevous step. If you got -1 in the prevous step then
a passes, if you got something else (extra square root of 1) then
a failed.
Of course, you repeat the test for number of different a.
> isn't prime). Given a Carmichael number it very quickly finds an
> extra square root of something, from which it promptly uses GCD to
> generate a partial factorization of the modulus (the Carmichael
> number).
>
> I'm thinking of generalizing all this to combine all prime factors
> of n-1 and such roots of all residues not just 1. One nice thing
> about this technique is that it doesn't require complete
> factorization of n-1. It's sufficient to find several small prime
> factors and try each of them for excess roots.
>
Well, if know reasonably large (of size comparable to (log n)^2)
divisor of n-1 then AKS method should work reasonably fast and
prove that n is prime. The hard cases are when n-1 has only
very small (say max 4) or very large divisors.
> Hey, here's a challenge to Dik, and anyone else who claims to use a
> really good test of primality. Tell me which of the following
> numbers you can prove prime or not-prime, and how you proved each:
I tried a few of them and the one I tried all pass many round of
Miller-Rabin. So I guess your question is how to prove that
they really are primes? They all seem to be of the form
n = 4*m + 1 with m having no small divisors. But it looks that
n+1 has a few divisors of reasonable size -- AFAICS enough to
make AKS practical. Also, for numbers of this size elliptic
curve method should give primality proof. However, those methods
require more time to code that I can spent now.
--
Waldek Hebisch
·······@math.uni.wroc.pl
From: robert maas, see http://tinyurl.com/uh3t
Subject: Re: Seeking efficient sequential-Carmichael-number generator
Date:
Message-ID: <rem-2007jan23-004@yahoo.com>
> From: Waldek Hebisch <·······@math.uni.wroc.pl>
> > At that point I decided to write a special function that did *only*
> > the check for too many square roots. But it'd detect too many
> > square roots of *any* number, not just too many square roots of 1.
> FYI, such test is a well-known improvement to Miller-Rabin test.
Ah! I'll take it as a compliment that I've re-invented something
that actually works and which some experts consider worthwhile.
> One possible example is:
> 1377161253229053 * 413148375987157
I'm not sure what it's supposed to be a example of. I tried the
random-base Fermat test five times, and it failed every time.
The only time the too-many-roots test can be used is when it passes
the Fermat test for at least one base, so you have a power of the
base which is 1, and can then work backwards from there seeing
which smaller powers of the base are *not* 1 even though the next
higher power *is* 1, and the complete lattice of powers from the
n-1 power back down to the 1 power (the base itself) is a small
finite set which can be easily traversed looking for roots of all
orders which are known factors of n-1. If you don't know any
particular power of the base which is 1, then working upward from
the base taking all sorts of chains of powers you have a lattice
which may almost entirely exhaust the interval [2,n-2], so you
might run for years before you get a result.
Well let me check if the Fermat test lies for any bases 2,3,5,...
(setq n (* 1377161253229053 413148375987157))
568971935244021120992707272321
* (exptmod 2 (+ -1 n) n)
190301149683473973336349312702
* (exptmod 3 (+ -1 n) n)
160292184450644624207793132819
* (exptmod 5 (+ -1 n) n)
146157731514288974408224711993
* (exptmod 7 (+ -1 n) n)
446261385180790040426377373293
* (exptmod 11 (+ -1 n) n)
265623271978363001386414860850
* (exptmod 13 (+ -1 n) n)
558068948768906866553639865022
Nope, it doesn't lie for any of them.
By the way, that first factor above is not prime.
(The second is, I proved it using Fermat-Maas test.)
So maybe the first factor above is a typo?
If it's not a typo, what's the complete prime factorization of this
example you've presented?
> > Do you know of *any* actually difficult-to-detect pseudoprimes, where:
> > - A large *majority* of random bases are Fermat liars.
> Theorem: n is either Carmichael or there is at most 50% Fermat liars
So I guess we're restricted to Carmichael numbers here.
> > - The number itself doesn't have any small factors that would yield
> > to brute-force trial division.
> > - No two powers of any small base have the same square that would
> > quickly yield to too-many-sqrts test.
> AFAICS you get too many sqrts if small numbers generate the whole
> Z/(nZ) group. Wikipedia:
> http://en.wikipedia.org/wiki/Miller-Rabin_primality_test
Unfortunately that Web page is full of illegible stuff like:
\mathbb
\left
\right
\cdot
making it impossible for me to figure out what it's trying to say.