mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Math

Reply
 
Thread Tools
Old 2011-03-08, 17:44   #23
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dartmouth NS

2·3·23·61 Posts
Default

Quote:
Originally Posted by Batalov View Post
...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
science_man_88 is offline   Reply With Quote
Old 2011-03-08, 18:52   #24
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dartmouth NS

2×3×23×61 Posts
Default

Quote:
Originally Posted by sascha77 View Post
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
science_man_88 is offline   Reply With Quote
Old 2011-03-08, 21:04   #25
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

5,987 Posts
Default

Quote:
Originally Posted by Batalov View Post
...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
CRGreathouse is offline   Reply With Quote
Old 2011-03-08, 21:51   #26
sascha77
 
sascha77's Avatar
 
Jan 2010
germany

2×13 Posts
Default

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.
sascha77 is offline   Reply With Quote
Old 2011-03-09, 00:10   #27
sascha77
 
sascha77's Avatar
 
Jan 2010
germany

2·13 Posts
Default

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):


<br />
      (2^{a}+2^{b})^{n-1} \equiv \;   (2^{a}+2^{b}) *        (2^{a}+2^{b})^{n-2}<br />

<br />
\equiv \;<br />
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}<br />
\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 \;<br />
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 \;<br />
2^{a+k}   * ( 2^{a+k}+2^{b+k})^{n-2} + 2^{b+k}  * (2^{a+k}+2^{b+k})^{n-2}

 \equiv<br />
(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)\; <br />
\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:

<br />
\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
sascha77 is offline   Reply With Quote
Old 2011-03-09, 00:13   #28
sascha77
 
sascha77's Avatar
 
Jan 2010
germany

2×13 Posts
Default

Quote:
Originally Posted by science_man_88 View Post
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.
sascha77 is offline   Reply With Quote
Old 2011-03-09, 02:53   #29
wblipp
 
wblipp's Avatar
 
"William"
May 2003
New Haven

3×7×113 Posts
Default

Quote:
Originally Posted by sascha77 View Post
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.
wblipp is offline   Reply With Quote
Old 2011-03-09, 02:56   #30
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

2×4,993 Posts
Default

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
Batalov is offline   Reply With Quote
Old 2011-03-09, 03:43   #31
R.D. Silverman
 
R.D. Silverman's Avatar
 
"Bob Silverman"
Nov 2003
North of Boston

23×937 Posts
Default

Quote:
Originally Posted by sascha77 View Post
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.
R.D. Silverman is offline   Reply With Quote
Old 2011-03-09, 06:32   #32
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

135438 Posts
Default

Quote:
Originally Posted by Batalov View Post
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.
CRGreathouse is offline   Reply With Quote
Old 2011-03-09, 14:07   #33
ATH
Einyen
 
ATH's Avatar
 
Dec 2003
Denmark

3,413 Posts
Default

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
ATH is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Number of distinct prime factors of a Double Mersenne number aketilander Operazione Doppi Mersennes 1 2012-11-09 21:16
A conjecture on a new property of Mersenne primes Thiele Math 18 2010-05-23 05:35
Number of Factors for a Mersenne Number kurtulmehtap Math 12 2010-05-03 14:02
Curious property of Mersenne numbers. arithmeticae Lounge 5 2008-10-27 06:15
A property of prime Mersenne numbers under LLT T.Rex Math 12 2005-09-12 07:56

All times are UTC. The time now is 17:55.


Mon Nov 28 17:55:04 UTC 2022 up 102 days, 15:23, 0 users, load averages: 1.42, 1.16, 1.12

Powered by vBulletin® Version 3.8.11
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.

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