Forum: Miscellaneous Math
2021-10-24, 19:40
|
|
Replies: 26
Views: 2,195
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...
|
|
Forum: Miscellaneous Math
2021-10-24, 18:09
|
|
Replies: 26
Views: 2,195
Reference
https://allquantor.at/blockchainbib/pdf/pietrzak2018simple.pdf
|
|
Forum: Miscellaneous Math
2021-10-24, 16:54
|
|
Replies: 26
Views: 2,195
Pieterzak's verifier
Pieterzak published an algorithm that verifies if x^(2^t)=y (mode N) without computing x^(2^t) (mode N). The new PRP algorithm avoids double cheking by using this verifier.
|
|
Forum: Miscellaneous Math
2021-10-24, 14:36
|
|
Replies: 26
Views: 2,195
Avoiding time-consuming exponantiating
Let us just assume that - for a given p - 3^(2^p)=9 (mode Mp) and check the assumption by Pietrzak's verifier. If the verifier does not find that the equality is true, then Mp isn't prime. This is...
|
|
Forum: Miscellaneous Math
2021-10-19, 10:42
|
|
Replies: 26
Views: 2,195
Accelerating PRP
Pietrzak's algorithm verifies if x^(2^t)=y (mode N) without actually calculating the exponent.
If Mp is prime then - by Fermat little theorm - n^(2^p)=n^2 (mode Mp).
The PRP algorithm computes...
|
|
Forum: Miscellaneous Math
2021-10-18, 16:54
|
|
Replies: 26
Views: 2,195
speeding up
PRP computes 3^(2^P) and then verifies the result. We suggest avoiding this computatin, which lasts for almost all the running time. This avoidance can speed up the search for prime Mp by an order of...
|
|
Forum: Miscellaneous Math
2021-10-18, 13:39
|
|
Replies: 26
Views: 2,195
a stupid question re: primality of mp
If mp is prime then we have n^(2^p)=n^2 (mod mp) for integer n.
To check primality of mp we may usu Pieterzak's verifer to verify 3^(2^p)=9 (mod mp). This can be done without the lengthy computation...
|
