Fermat's little theorem vs Mersenne

ktpn2011 · 2019-12-23, 19:13

Hello!

forgive me if.. i am just no-math person.
while programming, observed:

Fermat's little theorem for base 2 is not useful for 2^p -1 numbers, because it becomes test of p.
lets look on this form of FMA
2^(p-1) -1 = 0(mod p)

for 2^p -1 it will:

2^(2^p- 1) -1 = 0(mod (2^p- 1))

it becomes test of p, because both side has in binary form all bits set to 1;

first check 11 itself
(2^10 -1 ) / 11 = 1023 / 11 = 93

now for M11 = 2047

(2^2046 -1 ) / 2047
(2^2046 -1 ) in binary form is 1..1, count of 2046
2047 in binary form is 1..1, count of 11
so MOD function actually will do (2046 / 11)
and 2046 is doubled 1023, from FMA test of 11.

well, can't say about other base.

ktpn2011 · 2019-12-23, 19:30

I checked M11 for base 3 and 5, they eliminate M11 as not prime.

Batalov · 2019-12-23, 22:45

Quote:

Originally Posted by ktpn2011

I checked M11 for base 3 and 5, they eliminate M11 as not prime.

You are doing by hand what is called PRP tests (see paragaph 2). ალბათ პრემიერ ?

Yes, all Mersenne numbers (both Mersenne primes and Mersenne composites) are PRP base 2. So, there is absolutely no reason to run this test.

Yes, PRP base 3 is a reasonable "proxy" test (you still need to do the reat test later) for Mersenne primes. It gains popularity because it has "production value": it is robust (errors are caught fast) on computers regardless how reliably they are built. It is perfect for home computing; many home computers are overclocked, they make errors and the potential to catch these errors is excellent using a recent theoretical/practical solution.

retina · 2019-12-24, 04:27

Quote:

Originally Posted by ktpn2011

well, can't say about other base.

You can follow the same logic for other bases. What do numbers of the form 3^p-1 look like in base 3?

ktpn2011 · 2019-12-25, 19:29

thanks for replay.
Batalov, in page you pointed,
I wrote it, because as I feel, FMA function for base 2 "fails" for 2^p- 1 numbers.
But instead, 2047 is called "strong pseudoprime". I would call it "double pseudoprime" or fake :)

ewmayer · 2019-12-26, 23:23

For Fermat numbers F_m = 2^(2^m)+1, both the Fermat (a^(F_m-1) mod Fm) and Euler (a^((F_m-1)/2) mod Fm) pseudoprime tests are also useless to base a = 2, and are arguably more interestingly so than for the M(p) because the residue hits 1 after just the first m mod-squarings (i.e. to the base-2 log of the exponent) and stays pinned there, whereas a Fermat pseudoprime test of an M(p) to base 2 cycles through all possible (p-1) nonzero powers of 2 (mod M(p)) before hitting 1 on the final one. For the F_m if we switch to a = 3 again all is well, and even better, using the Euler test variant yields a rigorous primality test. (I'm currently working to propagate the Gerbicz-check mechanism to the Fermat-mod parts of my code, now that the Mersenne-PRP stuff has been released.)

Dr Sardonicus · 2019-12-27, 15:10

As discussed in this thread, any convenient quadratic residue modulo a prime M_p can be used for a pseudoprime test involving only repeated squaring (mod M_p).

Let M_p = 2^p - 1. Then M_p == 3 (mod 4). Thus, if M_p is prime and r is a quadratic residue (mod M_p),

r^(2^p-1) == r (mod M_p).

If p > 2 then r = -3 fills the bill, giving

3^(2^p-1) + 3 == 0 (mod M_p), if M_p is prime.

There is no guarantee that a composite M_p won't "pass" this test. However, running the simple Pari-GP script

forprime(p=3,12000,n=2^p-1;r=Mod(3,n)^(2^(p-1));if(r+3==0,print(p)))

shows that this test eliminates all composite M_p for 2 < p < 12000.

I don't know what the largest F_m tested by Pépin's test is, but my guess is that m is less than 30. The repeated squaring of 2 (mod p) can be used to test whether p divides F_m of course.

ewmayer · 2019-12-28, 04:25

Quote:

Originally Posted by ewmayer

...a Fermat pseudoprime test of an M(p) to base 2 cycles through all possible (p-1) nonzero powers of 2 (mod M(p)) before hitting 1 on the final one.

Things are actually a little more interesting than that ... if we consider the powers of 2 appearing in left-to-right modular binary exponentiation 2^(Mp-1) mod Mp, where Mp-1 = 11...110_2, excluding the final mod-squaring (since we always hit 0 on the penultimate step), we initialize our residue x=2 and do p-2 steps x = 2*x^2 (mod Mp). There is no need to actually do any squaring, since x is guaranteed to be a power of 2 at each step: x = 2^n, and in terms of the power n our base-2 Fermat-test iteration begins n = 1 and we do p-2 updates n = 2*n+1 (mod p). Thus for the first few odd primes p we have n-sequences

Code:

p	n-sequence
----	------------------------------------------
5	1,3,2,0
7	1,3,0,1,3,0
11	1,3,7,4,9,8,6,2,5,0
13	1,3,7,2,5,11,10,8,4,9,6,0
17	1,3,7,15,14,12,8,0 [repeat 2x]
19	1,3,7,15,12,6,13,8,17,16,14,10,2,5,11,4,9,0
23	1,3,7,15,8,17,12,2,5,11,0 [repeat 2x]
29	1,3,7,15,2,5,11,23,18,8,17,6,13,27,26,24,20,12,25,22,16,4,9,19,10,21,14,0
31	1,3,7,15,0 [repeat 6x]
37	1,3,7,15,31,26,16,33,30,24,12,25,14,29,22,8,17,35,34,32,28,20,4,9,19,2,5,11,23,10,21,6,13,27,18,0
41	1,3,7,15,31,22,4,9,19,39,38,36,32,24,8,17,35,30,20,0 [repeat 2x]
43	1,3,7,15,31,20,41,40,38,34,26,10,21,0, [repeat 3x]
47	1,3,7,15,31,16,33,20,41,36,26,6,13,27,8,17,35,24,2,5,11,23,0 [repeat 2x]
53	1,3,7,15,31,10,21,43,34,16,33,14,29,6,13,27,2,5,11,23,47,42,32,12,25,51,50,48,44,36,20,41,30,8,17,35,18,37,22,45,38,24,49,46,40,28,4,9,19,39,26,0
59	1,3,7,15,31,4,9,19,39,20,41,24,49,40,22,45,32,6,13,27,55,52,46,34,10,21,43,28,57,56,54,50,42,26,53,48,38,18,37,16,33,8,17,35,12,25,51,44,30,2,5,11,23,47,36,14,29,0
61	1,3,7,15,31,2,5,11,23,47,34,8,17,35,10,21,43,26,53,46,32,4,9,19,39,18,37,14,29,59,58,56,52,44,28,57,54,48,36,12,25,51,42,24,49,38,16,33,6,13,27,55,50,40,20,41,22,45,30,0

There does not appear to be any exploitable pattern with regard to the p-values yielding repeating subsequences, but here's a simple *nix bc function for anyone who wants to play with this (I went up to p = 1000):

Code:

define mpow2(p) {
	auto i, m, n, s;
	m = 2^p-1; n = 1; s = 0;
	print "For M(",p,") powers of 2 = ",n;
	for(i = 2; i < p; i++) {
		n = (n+n+1) % p;
		print ",",n;
		if(!n && !s) {
			s = i;	/* We have a repeating subsequence */
		}
	}
	if(s && s != (p-1)) {
		print " [subsequence of length (p-1)/",(p-1)/s," = ",s,"]";
	}
	print "\n";
}

Other Notes:
o n = (p-1) never appears in the sequence of powers of 2, irrespective of whether said sequence is repeating for the p in question or not. I leave it to the interested reader to figure out why.
o In cases with repeating subsequences, the repeat count is most often = 2, and the power of 2 appearing just before each 0 in the sequence is always n = (p-1)/2, due to the n = 2*n+1 (mod p) iteration.

@DrS: The modified Euler-test you describe is analogous to the modified Fermat test used by the GIMPS clients supporting PRP-with-Gerbicz check: instead of checking if a^(Mp-1) == 1 (mod Mp) we see if a^(Mp+1) == a^2 (mod Mp). (More precisely, we first compute a^(Mp+1) mod Mp then do 2 short-divs by the base a (mod Mp) to get the residue reported to the server, which is just the standard Fermat-test residue, i.e. 1 indicates a probable prime.) Since Mp+1 = 100...00_2 the modified test involves just mod-squarings.

Dr Sardonicus · 2019-12-28, 22:17

Quote:

Originally Posted by ewmayer

<snip>
There does not appear to be any exploitable pattern with regard to the p-values yielding repeating subsequences, but here's a simple *nix bc function for anyone who wants to play with this (I went up to p = 1000):
<snip>
o In cases with repeating subsequences, the repeat count is most often = 2, and the power of 2 appearing just before each 0 in the sequence is always n = (p-1)/2, due to the n = 2*n+1 (mod p) iteration.
<snip>

We know that 2^((p-1)/2) == 1 (mod p) precisely when p == 1 or 7 (mod 8), which is half the primes.

For n > 2, describing explicitly the primes p for which p == 1 (mod n) and 2^((p-1)/n) == 1 (mod p) is not possible with congruences, but we can state the proportion of primes with these properties.

If n is not divisible by 8, the proportion is $\frac{1}{n\varphi(n)}$ . If 8|n the proportion is $\frac{2}{n\varphi(n)}$ .

Dr Sardonicus · 2019-12-29, 14:37

Quote:

Originally Posted by ewmayer

<snip>
There does not appear to be any exploitable pattern with regard to the p-values yielding repeating subsequences,
<snip>
In cases with repeating subsequences, the repeat count is most often = 2, and the power of 2 appearing just before each 0 in the sequence is always n = (p-1)/2, due to the n = 2*n+1 (mod p) iteration.
<snip>

I compiled an exact count of the primes p, 2 < p < 50000000, for which 2 is a primitive root, and also those for which the multiplicative order o of 2 (mod p) is such that (p-1)/o has smallest prime factor q, q < 100.

We know that q = 2 is the smallest prime factor of (p-1)/o when p == 1 or 7 (mod 8).

If we treat the occurrences "2 is a q^th power residue (mod p)" as "independent" events for different q, we obtain simple formulas for (1) the proportion of primes p having 2 as a primitive root, and (2) the proportion of primes p for which 2 is not a primitive root, and q is the smallest prime factor of (p-1)/o; where, again, o is the multiplicative order of 2 (mod p).

Under this assumption, the proportion of primes p having 2 as a primitive root is given by Artin's constant,

$A \; = \; \prod_{p\text{ prime}}(1-\frac{1}{p(p-1)})\text{.}$

and the probability that 2 is not a primitive root (mod p) and q is the least prime factor of (p-1)/o is

$\frac{1}{q(q-1)}\prod_{p \; < \; q}(1-\frac{1}{p(p-1)})\text{.}$

The value of A is approximately 0.3739558.

I then computed the estimates obtained by these formulas. The results are as follows:

Exact count of p < 50000000 having 2 as primitive root: 1122370

Estimate using A*primepi(50000000): 1122292

Exact count of p < 50000000 for which 2 is not a primitive root, and least prime factor of (p-1)/o is [2, 3, 5, ... 97]

Code:

[1500339, 250129, 62658, 28206, 10380, 7375, 4205, 3301, 2300, 1392, 1253, 891, 660, 648, 513, 427, 335, 335, 258, 206, 209, 205, 164, 143, 123]

Estimate of same count using above formula:

Code:

[1500567, 250095, 62524, 28284, 10542, 7366, 4198, 3326, 2242, 1394, 1216, 848, 688, 624, 521, 409, 329, 308, 255, 226, 214, 183, 165, 144, 121]

2019-12-23, 19:13	#1
ktpn2011 Aug 2018 GEORGIA Republic 2²×7 Posts	Fermat's little theorem vs Mersenne Hello! forgive me if.. i am just no-math person. while programming, observed: Fermat's little theorem for base 2 is not useful for 2^p -1 numbers, because it becomes test of p. lets look on this form of FMA 2^(p-1) -1 = 0(mod p) for 2^p -1 it will: 2^(2^p- 1) -1 = 0(mod (2^p- 1)) it becomes test of p, because both side has in binary form all bits set to 1; first check 11 itself (2^10 -1 ) / 11 = 1023 / 11 = 93 now for M11 = 2047 (2^2046 -1 ) / 2047 (2^2046 -1 ) in binary form is 1..1, count of 2046 2047 in binary form is 1..1, count of 11 so MOD function actually will do (2046 / 11) and 2046 is doubled 1023, from FMA test of 11. well, can't say about other base.

2019-12-26, 23:23	#6
ewmayer ∂²ω=0 Sep 2002 República de California 103·113 Posts	For Fermat numbers F_m = 2^(2^m)+1, both the Fermat (a^(F_m-1) mod Fm) and Euler (a^((F_m-1)/2) mod Fm) pseudoprime tests are also useless to base a = 2, and are arguably more interestingly so than for the M(p) because the residue hits 1 after just the first m mod-squarings (i.e. to the base-2 log of the exponent) and stays pinned there, whereas a Fermat pseudoprime test of an M(p) to base 2 cycles through all possible (p-1) nonzero powers of 2 (mod M(p)) before hitting 1 on the final one. For the F_m if we switch to a = 3 again all is well, and even better, using the Euler test variant yields a rigorous primality test. (I'm currently working to propagate the Gerbicz-check mechanism to the Fermat-mod parts of my code, now that the Mersenne-PRP stuff has been released.) Last fiddled with by ewmayer on 2019-12-26 at 23:23

2019-12-27, 15:10	#7
Dr Sardonicus Feb 2017 Nowhere 11043₈ Posts	As discussed in this thread, any convenient quadratic residue modulo a prime M_p can be used for a pseudoprime test involving only repeated squaring (mod M_p). Let M_p = 2^p - 1. Then M_p == 3 (mod 4). Thus, if M_p is prime and r is a quadratic residue (mod M_p), r^(2^p-1) == r (mod M_p). If p > 2 then r = -3 fills the bill, giving 3^(2^p-1) + 3 == 0 (mod M_p), if M_p is prime. There is no guarantee that a composite M_p won't "pass" this test. However, running the simple Pari-GP script forprime(p=3,12000,n=2^p-1;r=Mod(3,n)^(2^(p-1));if(r+3==0,print(p))) shows that this test eliminates all composite M_p for 2 < p < 12000. I don't know what the largest F_m tested by Pépin's test is, but my guess is that m is less than 30. The repeated squaring of 2 (mod p) can be used to test whether p divides F_m of course. Last fiddled with by Dr Sardonicus on 2019-12-27 at 15:12 Reason: Omit unnecessary words!

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Modified Fermat's theorem	devarajkandadai	Number Theory Discussion Group	2	2017-06-23 04:39
abc conjecture and Fermat's Last Theorem	jasong	jasong	3	2012-10-24 08:45
Fermat's Theorem-tip of the iceberg?	devarajkandadai	Miscellaneous Math	2	2006-06-16 08:50
Fermat's Theorem	Crook	Math	5	2005-05-05 17:18
Fermat,s Theorem	devarajkandadai	Miscellaneous Math	3	2004-06-05 10:15

2019-12-23, 19:30	#2
ktpn2011 Aug 2018 GEORGIA Republic 2²×7 Posts	I checked M11 for base 3 and 5, they eliminate M11 as not prime.

2019-12-25, 19:29	#5
ktpn2011 Aug 2018 GEORGIA Republic 11100₂ Posts	thanks for replay. Batalov, in page you pointed, I wrote it, because as I feel, FMA function for base 2 "fails" for 2^p- 1 numbers. But instead, 2047 is called "strong pseudoprime". I would call it "double pseudoprime" or fake :)