Skip to content
Snippets Groups Projects
  • Simon Tatham's avatar
    18be6aec
    PrimeCandidateSource: remember prime factors of n-1. · 18be6aec
    Simon Tatham authored
    We already had a function pcs_require_residue_1() which lets you ask
    PrimeCandidateSource to ensure it only returns numbers congruent to 1
    mod a given value. pcs_require_residue_1_mod_prime() is the same, but
    it also records the number in a list of prime factors of n-1, which
    can be queried later.
    
    The idea is that if you're generating a DSA key, in which the small
    prime q must divide p-1, the upcoming provable generation algorithm
    will be able to recover q from the PrimeCandidateSource and use it as
    part of the primality certificate, which reduces the number of bits of
    extra prime factors it also has to make up.
    18be6aec
    History
    PrimeCandidateSource: remember prime factors of n-1.
    Simon Tatham authored
    We already had a function pcs_require_residue_1() which lets you ask
    PrimeCandidateSource to ensure it only returns numbers congruent to 1
    mod a given value. pcs_require_residue_1_mod_prime() is the same, but
    it also records the number in a list of prime factors of n-1, which
    can be queried later.
    
    The idea is that if you're generating a DSA key, in which the small
    prime q must divide p-1, the upcoming provable generation algorithm
    will be able to recover q from the PrimeCandidateSource and use it as
    part of the primality certificate, which reduces the number of bits of
    extra prime factors it also has to make up.