Quote:
Originally Posted by retina
The server creates a set of secret random primek values and computes the remainders.
Send the remainders to the client.
The clients task is to find the k values that generate the remainders.
Client sends the found k values to the server for verification.
How would that affect the client code if it needs to find some specific remainder values instead of just a remainder of zero, or the smallest remainder?
If you had one remainder then on average the client needs to run 50% of the work before finding the k value.
If you had two remainders then on average the client needs to run 75% of the work before finding both k values.
etc.
Considerations: The set of k values might not exactly match each other when two k values generate the same remainder, so just send one of them and the server can still verify the remainder is correct. The server doesn't need to remember the k values it chooses, just the remainders it sends.

This assumes that mfaktc always computes the residual. which it does not; mfaktc notices when the lower bits of the residual are not zero and doesn't calculate the upper bits so 90%+ of the time the full residual is never calculated.