mersenneforum.org a stupid question re: primality of mp
 Register FAQ Search Today's Posts Mark Forums Read

 2021-10-24, 19:40 #23 dov1093   Oct 2021 Israel 7 Posts Yes But they compute 3^(2^p) (mode Mp) and use the verifier to check the correctnes of the computation. We suggest that - as you don't need to know the concrete result of the computation but only if it equels 9 or not - don't do the computation: just use the verifier to see if it actually equels 9 or not. As we pointed out, this will accelerate the search for prime Mp by a huge factor..
 2021-10-26, 02:58 #24 LaurV Romulan Interpreter     "name field" Jun 2011 Thailand 231208 Posts If you can find a way to do that, than you are \$1000000 richer (yep, that is a million bucks), as you may have just solved "P versus NP" problem (at least partially). Or deterministic solution versus a non-deterministic solution. Things work like that: you have a problem that take a while to solve (like 3-sat, or hamiltonian cycle, or factorization, or even doing a PRP test**), but once solved by a third party, i.e. a magician comes and pulls a solution out of his ass hat, then it is very easy to verify that the solution is valid (like following the logic gates' output, or the hemiltonian path, or computing the product of the factors, or verifying the PRP residue). So, assuming we can build a magician, we won't need to do the PRP computation, but only to verify the result... ----- ** for nitpickers: mind that I didn't say that the "fac" or "prp" are np-complete Last fiddled with by LaurV on 2021-10-26 at 02:58
2021-10-26, 03:30   #25
kriesel

"TF79LL86GIMPS96gpu17"
Mar 2017
US midwest

10111000111102 Posts

Quote:
 Originally Posted by dov1093 This is done without comuting 3^(2^p) (mode Mp)!
How do you propose to run Pietrzak's verification, which employs 2v values of size p bits each, generated and saved along the way of computing 3^(2^p) (modulo Mp), where v is the verification proof power, without computing those values by computing 3^(2^p) (modulo Mp)? Or put another way, how do you propose to defeat the verifiable delay function? How do you propose to compute the verification function without its required inputs?

 2021-10-26, 04:23 #26 retina Undefined     "The unspeakable one" Jun 2006 My evil lair 2·23·137 Posts This is just the information time-travel ontology paradox thing, right? You take some information back in time and give to someone to invent some new (for that time) thing. Then after time passes and you are born and things, you take the information back in time "again" to complete the loop. And, magically, anti-gravity tech now exists. But where does the original information come from initially? You can't verify a proof if the proof doesn't exist yet. I'll leave it to you to wait for a time traveller from the future to pass you the proof files to verify.
2021-10-26, 05:45   #27
LaurV
Romulan Interpreter

"name field"
Jun 2011
Thailand

24×613 Posts

Quote:
 Originally Posted by retina But where does the original information come from initially?
What do you mean? From the magic hat. Didn't I tell you?

 Similar Threads Thread Thread Starter Forum Replies Last Post LaurV Information & Answers 14 2015-06-18 23:37 Uncwilly Lounge 19 2013-03-07 04:44 Biggles Prime Sierpinski Project 3 2006-02-07 22:50 rpropper GMP-ECM 15 2005-11-14 14:43 fropones Math 2 2003-05-28 00:44

All times are UTC. The time now is 15:39.

Tue Nov 30 15:39:40 UTC 2021 up 130 days, 10:08, 0 users, load averages: 2.06, 1.84, 1.67