 mersenneforum.org > Math Question about a mersenne-number property
 User Name Remember Me? Password
 Register FAQ Search Today's Posts Mark Forums Read  2011-03-08, 17:44   #23
science_man_88

"Forget I exist"
Jul 2009
Dumbassville

3×2,801 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
Dumbassville

3·2,801 Posts Quote:
 Originally Posted by sascha77 No. This is false. set p=11 -> for this:
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

5,987 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: 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) For every prime number and for every and with is the above congruation false with if 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 and with an same value k then the result will be the same. (Regardless if is prime or not) , is prime for every 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. ---> -------------------------------------------------------------------- ****************************************************** proof of (2): ****************************************************** proof of (3) : lets Define a function if we now do the function with the left and right side we get: The congruence is still the neutral element 1. And if we have found an a and an b so that the congruence is true: We can now because of (1) upper the variables a and b by a value k so that (a+k) = 0. We then have : ----> Now we use also here the function f(x): (First multiply then subtract one) Now subtract the number 1: Then we shift the exponents both back so that gets to its initial value we then have: 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
New Haven

237310 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 26D616 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,871 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) For every prime number and for every and with is the above congruation false with if 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 and with an same value k then the result will be the same. (Regardless if is prime or not) , is prime for every 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 3,391 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   Thread Tools Show Printable Version Email this Page 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 05:19.

Fri Oct 7 05:19:45 UTC 2022 up 50 days, 2:48, 0 users, load averages: 1.31, 1.23, 1.16

Copyright ©2000 - 2022, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.

≠ ± ∓ ÷ × · − √ ‰ ⊗ ⊕ ⊖ ⊘ ⊙ ≤ ≥ ≦ ≧ ≨ ≩ ≺ ≻ ≼ ≽ ⊏ ⊐ ⊑ ⊒ ² ³ °
∠ ∟ ° ≅ ~ ‖ ⟂ ⫛
≡ ≜ ≈ ∝ ∞ ≪ ≫ ⌊⌋ ⌈⌉ ∘ ∏ ∐ ∑ ∧ ∨ ∩ ∪ ⨀ ⊕ ⊗ 𝖕 𝖖 𝖗 ⊲ ⊳
∅ ∖ ∁ ↦ ↣ ∩ ∪ ⊆ ⊂ ⊄ ⊊ ⊇ ⊃ ⊅ ⊋ ⊖ ∈ ∉ ∋ ∌ ℕ ℤ ℚ ℝ ℂ ℵ ℶ ℷ ℸ 𝓟
¬ ∨ ∧ ⊕ → ← ⇒ ⇐ ⇔ ∀ ∃ ∄ ∴ ∵ ⊤ ⊥ ⊢ ⊨ ⫤ ⊣ … ⋯ ⋮ ⋰ ⋱
∫ ∬ ∭ ∮ ∯ ∰ ∇ ∆ δ ∂ ℱ ℒ ℓ
𝛢𝛼 𝛣𝛽 𝛤𝛾 𝛥𝛿 𝛦𝜀𝜖 𝛧𝜁 𝛨𝜂 𝛩𝜃𝜗 𝛪𝜄 𝛫𝜅 𝛬𝜆 𝛭𝜇 𝛮𝜈 𝛯𝜉 𝛰𝜊 𝛱𝜋 𝛲𝜌 𝛴𝜎𝜍 𝛵𝜏 𝛶𝜐 𝛷𝜙𝜑 𝛸𝜒 𝛹𝜓 𝛺𝜔