Tuesday, February 05, 2013

[ncojdkui] Fermat witness information content

It is mysterious that no information about the factorization of a composite number can be gained from a witness to compositeness in the Fermat primality test.  How is this statement proved?

I've never closely examined the result of modular exponentiation beyond testing whether or not it is unity.

It's probably related to the discrete logarithm problem being hard, but need to avoid circular reasoning.

(Factorizations can be obtained if the Miller-Rabin shortcut applies.)

No comments :