MM127

[science_man_88]

Originally Posted by Batalov

I might as well bury myself I'm useless either way at this point.

[ewmayer]

Originally Posted by ATH

But k is not always 4n+1. For example the factor 45315868721 of the exponent 566448359 I linked:
45315868721 = 2*40*566448359 + 1, so k=40 which is not 4n+1, and several of the other factors of that exponent does not fit k=4n+1 either.

In fact the only k's that never work for any prime exponent p are of the form k=4n+2, because those leads to factors 2kp+1 which is not +/1 (mod 8).

This is true even if we take into account the various relevant residue classes of the exponent in question: e.g. for MM31 and MM127 both exponents == 7 (mod 60). Looking at the table my TF code uses, this value of p%60 permits factors with k%60 = 0,5,8,9,12,17,20,24,29,32,33,44,45,48,53,57, which have k%4 = 0 or 1. And in fact the 4 known factors of MM31 have k = 68745, 20269004, 56474845800 and 41448832329225, i.e. we have 2 factors with each possible (mod 4) value.

#Fail

[Zeta-Flux]

Stan,

Consider the following example.

Let , which is prime. We see that is composite. Also is composite.

Next, the smallest such that is prime is which gives . This prime does not divide .

The problem in your file seems to come right near the end. There is no justification for the claim that divides . Everything else seemed okay (modulo minor mistakes). Sorry this didn't work out!

Now let me give you some advice. The first example where is prime, is composite, and is composite is when . It looks like you examined this case. But the very next case, when fails. In the future I recommend looking at multiple cases. (By the way, I also checked the next two cases , and they also fail.)

Sincerely,
Pace

[axn]

Originally Posted by Stan

Please supply a counterexample with k = 4n + 1 and I will have to think again.

p=47 is the first counterexample.
1223 is smallest prime of the form 2kp+1 = 7 (mod 8). k=13, lambda=3. However, it doesn't divide. The actual smallest prime of that form that does divide M(p) is 2351 (k=25, mu=6).

find_counter_example(p)=for(k=1,100, f=(8*k+2)*p+1; if(isprime(f), if(Mod(2,f)^p!=1, print("Counter example ", p, ":", k)); return));

forprime(p=3, 1001, if(p%4==3 && !isprime(2*p+1) && !isprime(2^p-1), find_counter_example(p)))

[ATH]

Originally Posted by ewmayer

This is true even if we take into account the various relevant residue classes of the exponent in question: e.g. for MM31 and MM127 both exponents == 7 (mod 60). Looking at the table my TF code uses, this value of p%60 permits factors with k%60 = 0,5,8,9,12,17,20,24,29,32,33,44,45,48,53,57, which have k%4 = 0 or 1. And in fact the 4 known factors of MM31 have k = 68745, 20269004, 56474845800 and 41448832329225, i.e. we have 2 factors with each possible (mod 4) value.

#Fail

Yeah, I know. It is true for +/-1,+/-7,+/-17,+/-23,+/-31,+/-41,+/-47,+/-49 (mod 120) but I did not want to start explaining that, so I just wrote +/- 1 (mod 8).

[Stan]

Many thanks axn, your pari program has, I think, found a factor of MM127 and therefore MM127 is composite. Could you please check the validity of the program and let me know what you think.
The program is:
find_example(p)=for(k=1,100,q=(8*k+2)*p+1;if(isprime(q),if(Mod(2,q)^p=1,print("Example ",q," : ",k));
p=2^127-1;find_example(p)
The program gives k = 14, q = 19396094914493492417412352623610788052879.
If it is correct, MM₁₂₇ has the factor q.

[legendarymudkip]

Originally Posted by Stan

Many thanks axn, your pari program has, I think, found a factor of MM127 and therefore MM127 is composite. Could you please check the validity of the program and let me know what you think.
The program is:
find_example(p)=for(k=1,100,q=(8*k+2)*p+1;if(isprime(q),if(Mod(2,q)^p=1,print("Example ",q," : ",k));
p=2^127-1;find_example(p)
The program gives k = 14, q = 19396094914493492417412352623610788052879.
If it is correct, MM₁₂₇ has the factor q.

2^2[SUP]127-1[/SUP]-1 mod 19396094914493492417412352623610788052879 is 12878846122774700542942977398640678236037, so no, it's not a factor.

[Stan]

Originally Posted by legendarymudkip

2^2[SUP]127-1[/SUP]-1 mod 19396094914493492417412352623610788052879 is 12878846122774700542942977398640678236037, so no, it's not a factor.

Then why does the pari program give 2^2[SUP]127-1[/SUP]=1 mod 19396094914493492417412352623610788052879?

[science_man_88]

Originally Posted by Stan

Many thanks axn, your pari program has, I think, found a factor of MM127 and therefore MM127 is composite. Could you please check the validity of the program and let me know what you think.
The program is:
find_example(p)=for(k=1,100,q=(8*k+2)*p+1;if(isprime(q),if(Mod(2,q)^p=1,print("Example ",q," : ",k));
p=2^127-1;find_example(p)
The program gives k = 14, q = 19396094914493492417412352623610788052879.
If it is correct, MM₁₂₇ has the factor q.

the code they gave you finds times your idea about the first prime of form 2*(4k+1)*p+1 dividing Mp doesn't work. the number you think is a factor is prime but does not divide MM127. it actually uses not equals though I didn't realize this either until after I ran it.

[legendarymudkip]

Originally Posted by Stan

Then why does the pari program give 2^2[SUP]127-1[/SUP]=1 mod 19396094914493492417412352623610788052879?

I'm not sure if it's the same in pari, but the "if(Mod(2,q)^p=1" seems to not be comparing for equality, but rather attempting an assignment, because of the use of = instead of ==. (I've never used pari so I don't know if it uses those operators to mean the same things) One thing that's certain is that it's not running Mod(2,q)^p, since 2 mod q is 2, and 2^p has 2^127-1 bits, or roughly 2^44 yottabytes of data, which exceeds all memory capacities at the moment. If it's using modular multiplication for every step I'm not sure what's going wrong. What does a print of Mod(2,q)^p give?

[science_man_88]

Originally Posted by legendarymudkip

I'm not sure if it's the same in pari, but the "if(Mod(2,q)^p=1" seems to not be comparing for equality, but rather attempting an assignment, because of the use of = instead of ==. (I've never used pari so I don't know if it uses those operators to mean the same things) One thing that's certain is that it's not running Mod(2,q)^p, since 2 mod q is 2, and 2^p has 2^127-1 bits, or roughly 2^44 yottabytes of data, which exceeds all memory capacities at the moment. If it's using modular multiplication for every step I'm not sure what's going wrong. What does a print of Mod(2,q)^p give?

you're correct From GP 2.7.3:

(18:16) gp > ??===
Comparison and Boolean operators:

   The six standard comparison operators <= , < , >= , > , == , != are available in GP.  The result is 1 if the comparison is true, 0 if it is false.  The operator == is quite liberal : for instance,
the integer 0, a 0 polynomial, and a vector with 0 entries are all tested equal.

   The extra operator === tests whether two objects are identical and is much stricter than == : objects of different type or length are never identical.

   For the purpose of comparison, t_STR objects are strictly larger than any other non-string type; two t_STR objects are compared using the standard lexicographic order.

   GP accepts < > as a synonym for != . On the other hand, = is definitely not a synonym for == : it is the assignment statement.

   The standard boolean operators || (inclusive or), && (and) and ! (not) are also available.