Re: More primality testing (was: Elementary group theory: Proof of Fermat-Maas ...)

robert maas, see http://tinyurl.com/uh3t a écrit :
An addendum to my earlier followup. You cited several large numbers
you believe to be prime, but which you can't prove prime, and
challeged me to try to prove them prime. I counter-challenge. Below
are several large numbers I've already proven to be prime. Can you
also prove them prime? Some are really easy to prove prime if you
know the trick, while others are much more difficult.

Difficult with a "N-1" method, not with ECPP (Elliptic Curve Primality
Proving).

744037861879306124158400228946593301184284063332387513639047222509291613663605412636622352860607874875271132641255257603

For the sake of comparison, certifying this number took 0.15s (see the
certificate at the end of the post) on AMD 3200+.

Now, concerning the method you use, I do not understand why you call it
"Fermat-Maas" (btw, giving one's name to one's theorem, even if it is an
original one, is generally a very efficient way to discredit one's work)
since I see no significative difference with the following one:

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

Moreover, from a practical point of view, it would seem you are doing
useless exponentiations. For instance, let say N-1 = 2*3*5*7*11*47.
According to the Pocklington theorem, after having set

F = 11*47 = 517
R = 2*3*5*7 = 210

(doing so, we have F >= R-1 and gcd(F,R)=1), if, for each prime p_i
of F there exists a b_i such that

gcd(b_i^((N-1)/p_i) - 1, N) = 1
and
b_i^(N-1) = 1 (mod N),

then N is prime.

Note that, so that the Pocklington theorem applies, it is required to
know a factored part F of N-1 greater than or equal to Sqrt(N) but there
are other theorems that require a smaller factored part.

mm


[PRIMO - Primality Certificate]
Version=3.0.2
WebSite=http://www.ellipsa.net/
Format=3
ID=B2E2203CF6D1B
Created=01/30/2007 05:45:25 PM
TestCount=19
Status=Candidate certified prime

[Running Times]
Initialization=0.00s
1stPhase=0.09s
2ndPhase=0.06s
Total=0.15s

[Candidate]
N$=49C33F88DCC2FDC6532C1D3C8F7F106EE635165E64FC11AB1EA5B5A208843A512D32DEE7D166D734B390B5E79D7AB1147603
HexadecimalSize=100
DecimalSize=120
BinarySize=399

[1]
Type=4
S$=46247CD5E5A44521
R$=10D36689CBF35D440C4BE844183EBBB05E47686A972BD325DF13E6C6FB324C050BE956C003E3BB2A42B5B
J$=16C6A69C3324AAB8FE70271673E6571496D422682B4F9A9FAF5E26ED5D53601D25B55C4DA303CCDE480A09B9290A1B7A84D
T$=1

[2]
Type=3
S$=9F4
R$=1B0C4C6B60C6500013C45F45AD9B199F560CB6522117D9A5BC40551961F2B6910B285C4C1693EBE441
A$=0
B$=3
T$=1

[3]
Type=3
S$=EAF96D90
R$=1D77E3C52807FF3586111890833F8DD29A557FFB05A706B8AEC90D3A8F24796293FDC55A8F
A$=0
B$=7
T$=1

[4]
Type=3
S$=289DA7
R$=B9BCD84228D83FA2BE611EC82F5921BE7CCAA2DA7AE1B21932C6D27AB4FA671644AB
A$=0
B$=-75DF8F14A01FFCD6184462420CFE374A6955FFEC169C1AE2BB2434EA3C91E58A4FF7156A4
T$=3

[5]
Type=3
S$=18789
R$=79712C5221521D42D67F3C088C9E5D9F59A3110DBEC11C9627C891CDCE56E223
A$=0
B$=10
T$=1

[6]
Type=4
S$=76A1A
R$=10610BEE96F0FFD60877037FE42A3E3925491DEA9E5ABFA95CE48660FBBB
J$=1C283E8A7C9BDF2E9DFA47733B2D75584F462DE840EF0A425340667CB8E4DF5
T$=1

[7]
Type=2
S$=24
R$=74793867BF95542AE6DC8AA9E4BA9E0825962A129EF71A09B103BB9537
Q$=2

[8]
Type=1
S$=9C6
R$=BEAD7BA65DDC1CEC66176590181CD754588B6BF6601F456F058C8E9
B$=2

[9]
Type=3
S$=4514409F4
R$=2C2A1B0C3014E1AAB828DD5E5E20B07C0439EA46C1277B9
A$=-23
B$=62
T$=3

[10]
Type=2
S$=4E
R$=90F337F37CFC543D701D182F27CDBFF2ED0CD985C225B
Q$=A

[11]
Type=4
S$=64EBE
R$=16FAF343669DAFEF01B385B9B4A7ED087708710DD
J$=-2275C92A7327E40A0F9570277D2415968665F0E815BF5
T$=1

[12]
Type=2
S$=65B4C93E
R$=39D7B447A868CEF9690BEF66D11EDFA31
Q$=6

[13]
Type=2
S$=2A
R$=160907B9C6404ED8EB10BCB9743C85F5
Q$=7

[14]
Type=3
S$=832
R$=2B052F0D7850A5A7781476E7C1771
A$=2
B$=0
T$=1

[15]
Type=2
S$=3A3AB2
R$=BD228333D9C7BDAED66B561
Q$=6

[16]
Type=2
S$=A2
R$=12AE13477DCE3256CC7C61
Q$=D

[17]
Type=3
S$=2304E650
R$=888E593E67DCE3
A$=0
B$=7
T$=1

[18]
Type=3
S$=9353BB
R$=ED48B0A7
A$=0
B$=10
T$=2

[19]
Type=0

[Signature]
1$=BF435A58BEC222CD2989C653886908307F91DDC0
2$=EF15072A170DB5560A052EA6EE754C8128A329C8
.