mersenneforum.org crazy Mersenne test
 Register FAQ Search Today's Posts Mark Forums Read

 2021-01-04, 22:53 #1 paulunderwood     Sep 2002 Database er0rr 22×13×71 Posts crazy Mersenne test If there exists a non-power of 2, k, such that Mod(k,n)^p==1 then n, a Mersenne number, is composite. E.g. n p=11, k=39; n p=23, k=156171. Is there any quick way to identify a k for a particular n? MODERATOR NOTE: I assumed n = 2^p - 1, and verified that Mod(39, 2047)^11 == 1 and Mod(156171,8388607)^23 == 1. Last fiddled with by Dr Sardonicus on 2021-01-05 at 00:02 Reason: Notational oopsadaisy
 2021-01-05, 00:25 #2 Dr Sardonicus     Feb 2017 Nowhere 11E516 Posts If n = 2^p - 1 is composite, there are k which are not powers of 2, such that Mod(k,n)^p ==1. If n = q*d, we can take i and j from 1 to p-1, with i<> j, and k = chinese(Mod(2^i,q),Mod(2^j,d)) There are (p-1)*(p-2) such pairs (i,j). So for 2^11 - 1 = 23*89, there are 10*9 = 90 values of k. If n = 2^p - 1 has f > 2 prime factors, the number of k is equal to the number of f-tuples of integers from 1 to p-1, not all of which are equal.
 2021-01-05, 00:31 #3 paulunderwood     Sep 2002 Database er0rr 22·13·71 Posts Counting the number of all solutions (including powers of 2) for p=11, 23, 29 seems to indicate that this count is equal to p^{#factors}. Last fiddled with by paulunderwood on 2021-01-05 at 00:36
2021-01-05, 00:49   #4
Dr Sardonicus

Feb 2017
Nowhere

32·509 Posts

Quote:
 Originally Posted by paulunderwood Counting the number of all solutions (including powers of 2) for p=11, 23, 29 seems to indicate that thus count is equal to p^{#factors}.
That would be correct. For each prime factor q of 2^p - 1, the group of elements of order p (mod q) is cyclic of order p, and is generated by Mod(2, q). So the group of elements of order p (mod 2^p - 1) is the direct product of #primefactors cyclic groups of order p.

I note that my count of non-powers of 2 was wrong. I failed to notice that you can take tuples of integers from 0 to p-1 as exponents (not 1 to p-1). So for 2 prime factors you get p*(p-1) non-powers of 2, and p powers of 2, one of which is 1.

If 2^p - 1 is divisible by q^m for m > 1, you use the group of order p generated by Mod(2, q^m). AFAIK not a single example of such a q is known for p prime, but there is no proof that none exists.

Last fiddled with by Dr Sardonicus on 2021-01-05 at 00:50

 2021-01-05, 01:00 #5 a1call     "Rashid Naimi" Oct 2015 Remote to Here/There 2·1,019 Posts Not sure if it is of any value but regardless to State the obvious: Mod(39, 2047)^11 == 1 Is another way of saying (2^11-1) | 39^11-1 Now if I am not mistaking 39-1 | 39^11-1 The candidate k's could be brute forced As (k-1)*(2^n-1)*c Choosing large k's should yield fastest results. Haven't verified if this is generally the case. Just my 2 cents which is worth less than 3 pence. Last fiddled with by a1call on 2021-01-05 at 01:01
2021-01-05, 01:51   #6
Viliam Furik

"Viliam Furík"
Jul 2018
Martin, Slovakia

3·52·7 Posts

Quote:
 Originally Posted by Dr Sardonicus There are (p-1)*(p-2) such pairs (i,j). So for 2^11 - 1 = 23*89, there are 10*9 = 90 values of k.
I have calculated 110 (11 * 10) non-2-power-values of k, under 2047. A big chunk of them were power-of-2 multiples of the smaller odd k's. Ignoring those, the number is 54.

This should be exactly all of them.
Code:
39
93
105
121
167
179
223
269
271
331
357
395
423
449
453
461
509
535
579
601
625
627
639
809
817
929
995
1043
1107
1113
1135
1159
1189
1221
1235
1291
1313
1337
1343
1521
1545
1577
1591
1603
1641
1669
1695
1819
1825
1871
1933
1959
2003
2025
There also seems to be a lot more (if not infinitely many) of the odd k's above 2047.

Did I misunderstand the value of 90?

 2021-01-05, 01:58 #7 bhelmes     Mar 2016 5·67 Posts I get other values and you could visualize them: http://devalco.de/System/system_natural.php?prim=2047
 2021-01-05, 02:06 #8 Viliam Furik   "Viliam Furík" Jul 2018 Martin, Slovakia 3×52×7 Posts I have found, that for p = 23, there is a smaller k, specifically 83663.
2021-01-05, 02:25   #9
Dr Sardonicus

Feb 2017
Nowhere

32×509 Posts

Quote:
 Originally Posted by Viliam Furik I have calculated 110 (11 * 10) non-2-power-values of k, under 2047. Did I misunderstand the value of 90?
No. I screwed up. I should have allowed the exponent of 2 to run from 0 to 10, not 1 to 10 as I originally did.
I wrote a mindless script to calculate the non-two-power k < 2^11 - 1:
Code:
? v=vector(110);k=0;for(i=0,10,for(j=0,10,if(i<>j,k++;v[k]=lift(chinese(Mod(2,23)^i,Mod(2,89)^j)))))

? print(vecsort(v))
[39, 78, 93, 105, 121, 156, 167, 179, 186, 210, 223, 242, 269, 271, 312, 331, 334, 357, 358, 372, 395, 420, 423, 446, 449, 453, 461, 484, 509, 535, 538, 542, 579, 601, 624, 625, 627, 639, 662, 668, 714, 716, 744, 790, 809, 817, 840, 846, 892, 898, 906, 922, 929, 968, 995, 1018, 1043, 1070, 1076, 1084, 1107, 1113, 1135, 1158, 1159, 1189, 1202, 1221, 1235, 1248, 1250, 1254, 1278, 1291, 1313, 1324, 1336, 1337, 1343, 1428, 1432, 1488, 1521, 1545, 1577, 1580, 1591, 1603, 1618, 1634, 1641, 1669, 1680, 1692, 1695, 1784, 1796, 1812, 1819, 1825, 1844, 1858, 1871, 1933, 1936, 1959, 1990, 2003, 2025, 2036]

 2021-01-05, 02:41 #10 LaurV Romulan Interpreter     Jun 2011 Thailand 22·2,381 Posts Isn't this the same like discrete logarithm? The "^11" (i.e. "^p") has not much to do there, any power can be used. If 2 is used, we are getting to the problem of finding the square root of 1 (mod m). Ex, for p=11, m=2^p+1, we have $$\pm 622$$ as one of the roots ($$622^2=1$$ (mod 2047)). A prime m will have only 2 roots (+1 and -1 (mod m)), while a composite m will have more roots depending on the number of factors. Now, if you can do that, you can also factor m (because in this case (r-1)(r+1)=0 (mod m) and you take the gcd with one of them, i.e. gcd(621,2047)=23, gcd(623,2047)=89). Using the 11th power is the same, except it is longer and a bit more complicate Last fiddled with by LaurV on 2021-01-05 at 02:42

 Similar Threads Thread Thread Starter Forum Replies Last Post Uncwilly PrimeNet 19 2019-04-11 19:13 thorken Software 66 2019-01-13 21:08 guido72 Software 6 2008-08-16 02:34 xago666 Information & Answers 2 2008-03-12 18:38 stippix Software 0 2004-04-22 08:55

All times are UTC. The time now is 21:35.

Sat Jun 12 21:35:32 UTC 2021 up 15 days, 19:22, 0 users, load averages: 1.52, 1.69, 1.63