mersenneforum.org > Math Question about a mersenne-number property
 Register FAQ Search Today's Posts Mark Forums Read

2011-03-08, 17:44   #23
science_man_88

"Forget I exist"
Jul 2009
Dartmouth NS

841810 Posts

Quote:
 Originally Posted by Batalov ...Is there a better mod exponent in Pari? Mod(2^a+2^b,n)^n ?
best for length on a line I could fine is this (for what you do in the x and x2 parts):
Code:
Mod(Mod(2^a+2^b,n)^2,n)
it also appears faster on my machine at the same a b and n values I used in my test.

Last fiddled with by science_man_88 on 2011-03-08 at 17:54

2011-03-08, 18:52   #24
science_man_88

"Forget I exist"
Jul 2009
Dartmouth NS

2×3×23×61 Posts

Quote:
 Originally Posted by sascha77 No. This is false. set p=11 ->$n=2^{p}-1 = 2047$ for this: $(2^{11}+2^{1})^{2046} \equiv (\;(2^{11} + 2^{1})\;mod(\;2047)\;)^{2046} \equiv 3^{2046} \equiv 1013\;(mod\; 2047)$
1013 is the sum of the first 9 Mersenne numbers with x being any x. wonder what happens for p=23

2011-03-08, 21:04   #25
CRGreathouse

Aug 2006

135438 Posts

Quote:
 Originally Posted by Batalov ...Is there a better mod exponent in Pari? Mod(2^a+2^b,n)^n ?
Mod(2,n)^a + Mod(2,n)^b. For the square of that, use (Mod(2,n)^a + Mod(2,n)^b)^2. You can reduce the caculations in the inner loop by lifting Mod(2,n) and Mod(2,n)^a out of the b loop: go from
Code:
{forprime(p=2,3000,
if(!isprime(n=2^p-1),
print(p);
for(a=1,p-1,
for(b=0,a-1,
x=(2^a+2^b)%n;
x2=(x^2)%n;
c=x;
for(i=1,p,
c=(c^2)%n
);
if(c==x2,print("found: a="a", b="b))
)
)
)
)}
to
Code:
{forprime(p=2,3000,
if(!isprime(n=2^p-1),
print(p);
two=Mod(2,n);
for(a=1,p-1,
t=two^a;
for(b=0,a-1,
c=t+two^b;
x2=c^2;
c=c^(2^p);
if(c==x2,print("found: a="a", b="b))
)
)
)
)}

Last fiddled with by CRGreathouse on 2011-03-08 at 21:11

 2011-03-08, 21:51 #26 sascha77     Jan 2010 germany 2·13 Posts I think we do not need to calculate more. Because I found out that if someone will find a counterexample with an a and an b so the other a's an b's must also fail for these n=2^p-1 (p prime). And the following: $3^{n-1} \equiv\;1\;(mod\; n)$ was from many people already intensive searched and no one has still found an composite number n=2^p-1 that holds the above congruation. So if we continue searching we would not find an counterexample because 3 = (2^0+2^1) I will in short try to give the proof about that.
 2011-03-09, 00:10 #27 sascha77     Jan 2010 germany 2×13 Posts I will now try to proof that if somebody have found an composite number n=2^p-1 (with p is prime) so that the congruence 'fails' then it must also fail for all the other a' and b's (with the same n) I did my best, but there are certainly some errors in it. So I will be glad if someone find these errors (in the proof) and let me now. I hope that these are not evil ones ;-) Ok. First I will introduce an equivalent conjecture which is much better : (1) $(2^{a}+2^{b})^{n-1}\; \equiv\; 1 \;(\;mod\;n)$ For every prime number $p$ and for every $a$ and $b$ with $0\le a \le p-2 \; , \; (a+1) \le b \le (p-1)$ is the above congruation false with $n=2^{p}-1$ if $n$ is not prime. (I do not want to proof that this conjecture is equivalent, we canjust take it as new conjecture) --------------------------------------------------------------------- Propositions: (2) If we add the two variables $a$ and $b$ with an same value k then the result will be the same. (Regardless if $n$ is prime or not) $n=2^{p}-1$ ,$p$ is prime $(2^{a+k}+2^{b+k})^{n-1}\; \equiv\; (2^{a}+2^{b})^{n-1}\;(\;mod\;n)$ for every $k \in N$ the congruence is true. ------------------------------------------------------------------ (3): If the congruence (1) is true for an a=a' and an b=b' then the congruence must also be true for a=a' and b=(b'+1) This means the variable a is the same but the variable b is by one greater as before. $(2^{a}+2^{b})^{n-1}\; \equiv\; 1 \;(\;mod\;n)$ ---> $(2^{a}+2^{b+1})^{n-1}\; \equiv\; 1 \;(\;mod\;n)$ -------------------------------------------------------------------- ****************************************************** proof of (2): $ (2^{a}+2^{b})^{n-1} \equiv \; (2^{a}+2^{b}) * (2^{a}+2^{b})^{n-2}$ $ \equiv \; 2^{a} * (2^{a}+2^{b})^{n-2} + 2^{b} * (2^{a}+2^{b})^{n-2}$ $\equiv \; 2^{a} * 1 * (2^{a}+2^{b})^{n-2} + 2^{b} * 1 * (2^{a}+2^{b})^{n-2} \equiv \; 2^{a} * (2^k)^{n-1} * (2^{a}+2^{b})^{n-2} + 2^{b} * (2^k)^{n-1} * (2^{a}+2^{b})^{n-2} \;$ $\equiv \;2^{a} * (2^k)^{n-2} * 2^{k} * (2^{a}+2^{b})^{n-2} + 2^{b} * (2^k)^{n-2} * 2^{k} * (2^{a}+2^{b})^{n-2}$ $\equiv \; 2^{a} * 2^{k} * (2^{k} * (2^{a}+2^{b}))^{n-2} + 2^{b} * 2^{k} * (2^{k} * (2^{a}+2^{b}))^{n-2}$ $\equiv \; 2^{a+k} * ( 2^{a+k}+2^{b+k})^{n-2} + 2^{b+k} * (2^{a+k}+2^{b+k})^{n-2}$ $\equiv (2^{a+k}+2^{b+k})^{n-1}$ ****************************************************** proof of (3) : lets Define a function$f(x) = 2*x-1$ if we now do the function with the left and right side we get: $f( (2^{a}+2^{b})^{n-1}) \; \equiv\; f(1) \;(\;mod\;n)$ $2*(2^{a}+2^{b})^{n-1}-1\; \equiv\; 1 \;(\;mod\;n)$ The congruence is still the neutral element 1. And if we have found an a and an b so that the congruence is true: $(2^{a}+2^{b})^{n-1}\; \equiv\; 1 \;(\;mod\;n)$ We can now because of (1) upper the variables a and b by a value k so that (a+k) = 0. We then have : $(2^{0}+2^{b'})^{n-1}\; \equiv\; 1 \;(\;mod\;n)$ ----> $(2^{0}+2^{b'})^{n}\; \equiv\; 2^{0}+2{b'} \;(\;mod\;n)$ Now we use also here the function f(x): (First multiply then subtract one) $2^{0}+2^{b'} \;(\;mod\;n)\; / * 2$ $\equiv \; 2^{1}+2^{b'+1} \;(\;mod\;n)\;$ Now subtract the number 1: $\equiv \; 2^{1}+2^{b'+1} \;\;-1 \; \equiv \; 2^{0}+2^{b'+1} \;(\;mod\;n)\; $ $\equiv (2^{0}+2^{b'+1})^{n} \; (\;mod \; n)$ Then we shift the exponents both back so that $2^{(0)}$ gets to its initial value $2^{(a)}$ we then have: $ \equiv (2^{a}+2^{b+1})^{n} \; (\;mod \; n)$ And if we do recursive this method we can make the distance between a and b as big as we want. ******************************************************* Last fiddled with by sascha77 on 2011-03-09 at 00:22
2011-03-09, 00:13   #28
sascha77

Jan 2010
germany

2·13 Posts

Quote:
 Originally Posted by science_man_88 1013 is the sum of the first 9 Mersenne numbers with x being any x. wonder what happens for p=23
I do not know exactly what you mean.
Is it possible that you show me your idea with an example ?

thanks.

2011-03-09, 02:53   #29
wblipp

"William"
May 2003
Near Grandkid

2×1,187 Posts

Quote:
 Originally Posted by sascha77 I think we do not need to calculate more.
Are you still working on this? See Bob Silverman's hint in post #3. It follows VERY quickly from that hint.

 2011-03-09, 02:56 #30 Batalov     "Serge" Mar 2008 Phi(4,2^7658614+1)/2 1005910 Posts Are there any* known false witnesses for 2p-1 with prime p>11? ____________ *any, not necessarily with Hamming weight 2 EDIT: yes. I've stepped out of pfgw (which only works with bases <=255) and with Pari, 'found' one: 349 for 2^29-1. It is probably known. And then many for 2^23-1 and many more for 2^29-1... Last fiddled with by Batalov on 2011-03-09 at 03:46
2011-03-09, 03:43   #31
R.D. Silverman

"Bob Silverman"
Nov 2003
North of Boston

22×1,877 Posts

Quote:
 Originally Posted by sascha77 I will now try to proof that if somebody have found an composite number n=2^p-1 (with p is prime) so that the congruence 'fails' then it must also fail for all the other a' and b's (with the same n) I did my best, but there are certainly some errors in it. So I will be glad if someone find these errors (in the proof) and let me now. I hope that these are not evil ones ;-) Ok. First I will introduce an equivalent conjecture which is much better : (1) $(2^{a}+2^{b})^{n-1}\; \equiv\; 1 \;(\;mod\;n)$ For every prime number $p$ and for every $a$ and $b$ with $0\le a \le p-2 \; , \; (a+1) \le b \le (p-1)$ is the above congruation false with $n=2^{p}-1$ if $n$ is not prime. (I do not want to proof that this conjecture is equivalent, we canjust take it as new conjecture) --------------------------------------------------------------------- Propositions: (2) If we add the two variables $a$ and $b$ with an same value k then the result will be the same. (Regardless if $n$ is prime or not) $n=2^{p}-1$ ,$p$ is prime $(2^{a+k}+2^{b+k})^{n-1}\; \equiv\; (2^{a}+2^{b})^{n-1}\;(\;mod\;n)$ for every $k \in N$ the congruence is true.

You are disguising what is going on. All you have done is multiply
(2^a + 2^b)^(n-1) by 2^(k(n-1)) [all mod n]

But 2^(n-1) = 1 for all n = 2^p-1, even when 2^p-1 isn't prime, because
2 is always a false withness for 2^p-1.

I will look at the rest later. I am sleepy at the moment.

2011-03-09, 06:32   #32
CRGreathouse

Aug 2006

10111011000112 Posts

Quote:
 Originally Posted by Batalov Are there any* known false witnesses for 2p-1 with prime p>11?
Sure -- are there any composite 2p - 1, p > 11 prime, lacking false witnesses?

Depending on how you count it, 2[SUP]23[/SUP] - 1 has 1056, 1057, or 1058 false witnesses. 2[SUP]29[/SUP] - 1 has over a hundred thousand.

 2011-03-09, 14:07 #33 ATH Einyen     Dec 2003 Denmark 19·181 Posts I find the subject of witness and false/non-witness for Miller-Rabin test interesting. I found this paper with 2 conjectures on oeis.org: http://www.ma.iup.edu/MAA/proceedings/vol1/higgins.pdf http://oeis.org/A090659 His conjectures includes 1 as a non-witness for all numbers. Conjecture 1 checks out for all 168,331 n=p*q<10^6 where p,q are distinct primes. Conjecture 2 checks out for n=p*q<5*10^8 p,q primes where p=2r+1, q=4r+1=2p-1 and r odd. I have my own conjecture for n=p^2, p prime: The number of non-witnesses is p-1, and they are pairwise symmetric about p^2/2, the 1st is 1 and the p-1'th is p^2-1. If we call the k'th non-witness nw(k) then: nw(k)+nw(p-k) = p^2. It is only based on computations not on heuristics or any attempt to prove it. Last fiddled with by ATH on 2011-03-09 at 14:11

 Similar Threads Thread Thread Starter Forum Replies Last Post aketilander Operazione Doppi Mersennes 1 2012-11-09 21:16 Thiele Math 18 2010-05-23 05:35 kurtulmehtap Math 12 2010-05-03 14:02 arithmeticae Lounge 5 2008-10-27 06:15 T.Rex Math 12 2005-09-12 07:56

All times are UTC. The time now is 23:03.

Mon Feb 6 23:03:54 UTC 2023 up 172 days, 20:32, 1 user, load averages: 1.15, 1.11, 1.05