News for hackers. Stuff that matters.

A comment on R49081 Is Prime. Parent comment

Re:R49081 Is Prime by incompatible on Sunday November 20, 2022 @11:57PM (#33688959)
Certification is the creation of a proof that the number is prime (consisting of some related numbers), while the verification checks that the certification is correct?
[ Parent | on HN ]
Re:R49081 Is Prime by saghm on Monday November 21, 2022 @01:48AM (#33689611)
I was thinking that "certification" referred to ensuring that the program they wrote to test it was correct, and then verifying was running it, but your interpretation makes sense too
[ Parent | on HN ]
Re:R49081 Is Prime by segfaultbuserr on Monday November 21, 2022 @02:21AM (#33689803)
Yes. In particular, "certification" refers to the fact that the proof is computationally difficult to create, but once it's created, it's easy for a third-party to check its correctness (insert your P/NP reference here).

https://en.wikipedia.org/wiki/Primality_certificate

[ Parent | on HN ]