mersenneforum.org  

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

Reply
 
Thread Tools
Old 2020-06-04, 07:23   #67
R. Gerbicz
 
R. Gerbicz's Avatar
 
"Robert Gerbicz"
Oct 2005
Hungary

29×47 Posts
Default

Quote:
Originally Posted by LaurV View Post
This doesn't make sense. 997 is prime. Is my "reserved task" to test if 997 is prime? or to test if 2^997-1 is prime?
There is nothing special in 997, for composite/prime the proof check should run in the same way.

Quote:
Originally Posted by LaurV View Post
Examples of M and B that pass the test, as you described it:
249 and 804 - these are 3^(2^250) (mod 997) and 3^(2^500) (mod 997), of course, provided just for fun; what follows are random values, generated like described, pick a random M=B and run for(i=1,250,B=B^2), print M and B. Pick your favorite.
Asked one. But let's take not the first because you could complain why. Picked the (5,718)

Code:
check_proof(M,B,N,top,A=3,num_iteration=20,maxh=1000)={
for(i=1,num_iteration,h=1+random(maxh);
res=Mod(A,N)^h*M;
res=res^(2^(top/2));
res2=Mod(M,N)^h*B;
print1("Test#"i": h=",h);
if(res==res2,print(" passed the test"),print(" failed the test")))}

? check_proof(5,718,997,500)
Test#1: h=250 failed the test
Test#2: h=992 failed the test
Test#3: h=235 failed the test
Test#4: h=283 failed the test
Test#5: h=116 failed the test
Test#6: h=832 failed the test
Test#7: h=159 failed the test
Test#8: h=133 failed the test
Test#9: h=487 failed the test
Test#10: h=310 failed the test
Test#11: h=568 failed the test
Test#12: h=565 failed the test
Test#13: h=352 failed the test
Test#14: h=269 failed the test
Test#15: h=580 failed the test
Test#16: h=22 failed the test
Test#17: h=601 failed the test
Test#18: h=992 failed the test
Test#19: h=162 failed the test
Test#20: h=136 failed the test
? 
? check_proof(249,804,997,500)
Test#1: h=548 passed the test
Test#2: h=453 passed the test
Test#3: h=720 passed the test
Test#4: h=551 passed the test
Test#5: h=938 passed the test
Test#6: h=468 passed the test
Test#7: h=40 passed the test
Test#8: h=480 passed the test
Test#9: h=562 passed the test
Test#10: h=942 passed the test
Test#11: h=457 passed the test
Test#12: h=911 passed the test
Test#13: h=742 passed the test
Test#14: h=381 passed the test
Test#15: h=187 passed the test
Test#16: h=208 passed the test
Test#17: h=991 passed the test
Test#18: h=660 passed the test
Test#19: h=240 passed the test
Test#20: h=310 passed the test
?
You failed all 20 tests.
Now it is your turn. (In the second run used the true pair to check my proof checker.
R. Gerbicz is offline   Reply With Quote
Old 2020-06-04, 07:32   #68
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
Jun 2011
Thailand

2·5·859 Posts
Default

Quote:
Originally Posted by preda View Post
If you do that, my verification will catch your cheating right away. The verification checks both halves, covers all the iterations, and as such does detect your cheat attempt easily.

Let me try to explain why your cheat attempt is detected:

3 is the base (starting point) of the PRP test.

prp(3^h * M, k) == prp(3^h, k) * prp(M, k) == prp(3, k)^h * B
(because prp(M, k) == B (B is "F" in your naming))

The verification compares for equality:
prp(3, k)^h * B == M^h * B,

which would pass if prp(3, k) == M.
But as you chose M "at random" the verification above fails with high probability, and your cheat it detected.

Does this make sense? I'm sure you could have worked through the above algebra without the hand-holding.
This doesn't make sense either. Why do you need B? you can simplify it in both sides. If that is true, you just found a method to run the PRP test in half number of iterations than required. This is just a proof of work of the fact that I start from M and I get B after a number of iterations. But there is no way for you (that we know of) to test if M is correct (i.e. it represents indeed the residue after 250 iterations, in Robert's example). IF you would have any procedure/function/algorithm f(R,k) to test if residue R is the right residue after k iterations and give you true or false, then why don't you just run this function for the last residue (996 in the example) and don't need any other verification?


I begin to believe that I am stupid, but really, I don't get this. Please provide an example with numbers, for a PRP of a mersenne number with a small exponent. Even M29 or M41 would be right.
LaurV is offline   Reply With Quote
Old 2020-06-04, 07:35   #69
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
Jun 2011
Thailand

218E16 Posts
Default

Quote:
Originally Posted by R. Gerbicz View Post
Now it is your turn. (In the second run used the true pair to check my proof checker.
Wait! Crosspost.
Let me digest this!

Last fiddled with by LaurV on 2020-06-04 at 07:35
LaurV is offline   Reply With Quote
Old 2020-06-04, 08:40   #70
R. Gerbicz
 
R. Gerbicz's Avatar
 
"Robert Gerbicz"
Oct 2005
Hungary

29·47 Posts
Default

Quote:
Originally Posted by LaurV View Post
This doesn't make sense either. Why do you need B? you can simplify it in both sides.
There are flaws in that post, but probably all previous posts were good, used the same notations from Preda: https://mersenneforum.org/showpost.p...3&postcount=15

the verification for a pair of residue: prp(A^h * M, topK/2) == M^h * B.
(in my code top=topK and used N for modulus).
And it is a false that the test is passing only for the true (M,B) pair.
R. Gerbicz is offline   Reply With Quote
Old 2020-06-04, 11:41   #71
preda
 
preda's Avatar
 
"Mihai Preda"
Apr 2015

21168 Posts
Default

Quote:
Originally Posted by LaurV View Post
This doesn't make sense either. Why do you need B? you can simplify it in both sides. If that is true, you just found a method to run the PRP test in half number of iterations than required. This is just a proof of work of the fact that I start from M and I get B after a number of iterations. But there is no way for you (that we know of) to test if M is correct (i.e. it represents indeed the residue after 250 iterations, in Robert's example). IF you would have any procedure/function/algorithm f(R,k) to test if residue R is the right residue after k iterations and give you true or false, then why don't you just run this function for the last residue (996 in the example) and don't need any other verification?


I begin to believe that I am stupid, but really, I don't get this. Please provide an example with numbers, for a PRP of a mersenne number with a small exponent. Even M29 or M41 would be right.
Proof by example it is then.
Python3 and modulo M7
Code:
$ python3
>>> A=3
>>> B=3**64 % 127
>>> M=3**8 % 127
>>> h=5
>>> (A**h * M) ** 8 % 127 == (M**h * B) % 127
True
>>> M=42
>>> B=M**8 % 127
>>> (A**h * M) ** 8 % 127 == (M**h * B) % 127
False
>>> M=13
>>> B=M**8 % 127
>>> (A**h * M) ** 8 % 127 == (M**h * B) % 127
False
preda is offline   Reply With Quote
Old 2020-06-04, 11:52   #72
retina
Undefined
 
retina's Avatar
 
"The unspeakable one"
Jun 2006
My evil lair

554110 Posts
Default

Quote:
Originally Posted by preda View Post
Proof by example it is then.
Python3 and modulo M7
Code:
$ python3
>>> A=3
>>> B=3**64 % 127
>>> M=3**8 % 127
>>> h=5
>>> (A**h * M) ** 8 % 127 == (M**h * B) % 127
True
>>> M=42
>>> B=M**8 % 127
>>> (A**h * M) ** 8 % 127 == (M**h * B) % 127
False
>>> M=13
>>> B=M**8 % 127
>>> (A**h * M) ** 8 % 127 == (M**h * B) % 127
False
Zero is the only other value here that satisfies the condition:
Code:
A=3
h=5
N=127
e=8
print("Correct value {}".format(A**e % N))
for M in range(0,N):
	B=M**e % N
	if (A**h * M) ** e % N == (M**h * B) % N: print("Found {}".format(M))
Output:
Code:
Correct value 84
Found 0
Found 84
retina is online now   Reply With Quote
Old 2020-06-05, 00:32   #73
preda
 
preda's Avatar
 
"Mihai Preda"
Apr 2015

100010011102 Posts
Default AWS outbound data transfer cost

I don't have experience with AWS and the pricing on their website is not easy to understand.

Could somebody please inform me, how much would it cost to transfer 50GB/day out of AWS, for example by doing HTTP/HTTPS PUT or PUSH to a server that is not in AWS, with a 150MB size per request if that's relevant. (or is there a better way to transfer such data out of AWS?)
preda is offline   Reply With Quote
Old 2020-06-06, 06:13   #74
preda
 
preda's Avatar
 
"Mihai Preda"
Apr 2015

2×19×29 Posts
Default topK under vs. above the exponent E

There is a problem with storing the res64 in the proof file header: if the proof file is public, then the proof reveals the res64, which is supposed to be "secret" in the classic DC setup.

Even without explicitly storing the res64 in the proof header, the proof does store the residue at iteration topK. As topK is under the exponent E (and very close), somebody can simply run a the few iterations from topK to E and thus discover the res64, which again weakens the classic DC which relies on the res64 being "secret" until DCed.

An alternative is to set topK to be above E (specifically, let topK be the smallest multiple of 1024 that is larger than E). Let's see what is the impact of this change:

First, through the same "proof verificatication" algorithm the verifier can verify that the residue at topK is correct. OTOH the verifier is not able anymore to derive the residue at E, or the res64. Depending on how you look at it, this inability of the verifier to derive the residue at E may seem like something lost (the proof does not allow to derive res64 anymore) or like something gained (the verification does not reveal res64 anymore).

In addition to verifying that the residue at topK is correct, we would like to also be able to establish the mersenne candidate status (composite or PRP) based on the proof. We can still do this: if the candidate is PRP, then the residue at E must be 9. So the verifier can run the iterations from E up to topK starting with residue 9, and compare the residues at topK. If equality, the candidate is PRP, othewise it's composite.

But.. there is one more point: the proof also exposes the residue M0 (the first middle) which can also be used as a starting point for iterating up towards E. This allows to compute the res64 with only half the iterations of a classic PRP DC.

I think we shouldn't sweat over revealing res64 through the proof (or, to be precise, revealing the least significant byte of the res64, which is the only one that's secret), because, once an exponent has a proof available, we can base the DC of that exponent on the proof verification and discount the value of the classic DC (for the particular exponent that has a proof).

So, to recap:
A) topK under E: allows to extract from the proof res64 type1, type4, res2048, full-residue at E. Reveals res64.
B) topK above E: does not reveal res64, and does not allow computing either of those (except by doing one half-PRP starting from M[0]).

Oppinions?
preda is offline   Reply With Quote
Old 2020-06-06, 07:29   #75
preda
 
preda's Avatar
 
"Mihai Preda"
Apr 2015

2·19·29 Posts
Default

Quote:
Originally Posted by preda View Post
There is a problem with storing the res64 in the proof file header: if the proof file is public, then the proof reveals the res64, which is supposed to be "secret" in the classic DC setup.

Even without explicitly storing the res64 in the proof header, the proof does store the residue at iteration topK. As topK is under the exponent E (and very close), somebody can simply run a the few iterations from topK to E and thus discover the res64, which again weakens the classic DC which relies on the res64 being "secret" until DCed.

An alternative is to set topK to be above E (specifically, let topK be the smallest multiple of 1024 that is larger than E). Let's see what is the impact of this change:

First, through the same "proof verificatication" algorithm the verifier can verify that the residue at topK is correct. OTOH the verifier is not able anymore to derive the residue at E, or the res64. Depending on how you look at it, this inability of the verifier to derive the residue at E may seem like something lost (the proof does not allow to derive res64 anymore) or like something gained (the verification does not reveal res64 anymore).

In addition to verifying that the residue at topK is correct, we would like to also be able to establish the mersenne candidate status (composite or PRP) based on the proof. We can still do this: if the candidate is PRP, then the residue at E must be 9. So the verifier can run the iterations from E up to topK starting with residue 9, and compare the residues at topK. If equality, the candidate is PRP, othewise it's composite.

But.. there is one more point: the proof also exposes the residue M0 (the first middle) which can also be used as a starting point for iterating up towards E. This allows to compute the res64 with only half the iterations of a classic PRP DC.

I think we shouldn't sweat over revealing res64 through the proof (or, to be precise, revealing the least significant byte of the res64, which is the only one that's secret), because, once an exponent has a proof available, we can base the DC of that exponent on the proof verification and discount the value of the classic DC (for the particular exponent that has a proof).

So, to recap:
A) topK under E: allows to extract from the proof res64 type1, type4, res2048, full-residue at E. Reveals res64.
B) topK above E: does not reveal res64, and does not allow computing either of those (except by doing one half-PRP starting from M[0]).

Oppinions?
Thinking more about it I think I start to like the variant with topK above E more, as being potentially more resilient againts errors (including programming errors), because the computation that takes place during verification does not retrace the steps of the PRP test to any degree.

While a res64-at-topK for the prime case can be computed independently of the proof, even ahead of time (being prp(3, topK - E +1)).
preda is offline   Reply With Quote
Old 2020-06-08, 17:37   #76
R. Gerbicz
 
R. Gerbicz's Avatar
 
"Robert Gerbicz"
Oct 2005
Hungary

101010100112 Posts
Default

Quote:
Originally Posted by R. Gerbicz View Post
You failed all 20 tests.
Now it is your turn. (In the second run used the true pair to check my proof checker.
The true pair was (249,804), in the follow-up consider another pair (748,193):
Code:
?  check_proof(748,193,997,500)
Test#1: h=780 failed the test
Test#2: h=613 passed the test
Test#3: h=978 failed the test
Test#4: h=816 failed the test
Test#5: h=21 passed the test
Test#6: h=637 passed the test
Test#7: h=781 passed the test
Test#8: h=236 failed the test
Test#9: h=828 failed the test
Test#10: h=523 passed the test
Test#11: h=85 passed the test
Test#12: h=472 failed the test
Test#13: h=520 failed the test
Test#14: h=419 passed the test
Test#15: h=776 failed the test
Test#16: h=410 failed the test
Test#17: h=967 passed the test
Test#18: h=530 failed the test
Test#19: h=986 failed the test
Test#20: h=73 passed the test
9 passed, and 11 failed, so in 9/20 we successfully faked the proof checker, and note that this trap holds for more than two residues, say when you have 512 residues or more!

Last fiddled with by R. Gerbicz on 2020-06-08 at 17:39 Reason: typo
R. Gerbicz is offline   Reply With Quote
Old 2020-06-08, 18:07   #77
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
Jun 2011
Thailand

2×5×859 Posts
Default

Well, no need to continue here, you convinced me

My initial understanding of what you (and Mihai) wanted to do was wrong, and the piece of code you provided enlightened me. Now it is much clear, and I played a bit withe the math too. For primes (like provided examples) there are only two square roots of 1, no other pair will match. For composites, especially with many factors) there can be multiple matches (it is related to the number of roots of 1), but yet, finding these matches, i.e. the effort to "fake" the test, is an exponential process; with my limited knowledge, I don't see right now how the test can be faked without trying a lot of pairs, so for large enough numbers, it is MUCH faster to do the test than to try to fake it. You are totally right.
LaurV is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
phi function rula Homework Help 3 2017-01-18 01:41
delay in crediting? ixfd64 PrimeNet 7 2008-10-20 20:45
Why delay between posts? JHagerson Forum Feedback 1 2006-05-13 21:30
Minimum delay between server connections vaughan ElevenSmooth 5 2005-09-08 17:17
Stats delay ltd Prime Sierpinski Project 10 2005-08-08 13:38

All times are UTC. The time now is 04:52.

Tue Jul 14 04:52:47 UTC 2020 up 111 days, 2:25, 0 users, load averages: 2.01, 1.83, 1.93

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, 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.