3 ms·
The results aren't verfied by running the same calculations again. Rather, there's a verification method used along with some information from the original solu
by cedilla 4y ago
The results aren't verfied by running the same calculations again. Rather, there's a verification method used along with some information from the original solution - that's the certificate they mention.
Imagine factoring a non-prime number. It would take you quite long to factor 695587 with nothing but a cheap calculator, but you could very quickly verify my factorization if I give you the information that it is divisible by 71 and 101.
- dspillett 4y agoThough the factor-checking like verification won't work for “this number is prime” the same as it will for “this number is not prime”. A test that results in saying a number is prime doesn't output any factors to test because if such existed the number would not be prime. I'll have to read up on the certification/verification process to comment any further though.
- cedilla 4y agoIt does work that way, just not as straightforwardly. See https://en.wikipedia.org/wiki/Certificate_%28complexity%29 https://en.wikipedia.org/wiki/Certificate_%28complexity%29 if you're interested in learning more.