• Login
    View Item 
    •   SMARTech Home
    • College of Computing (CoC)
    • College of Computing Technical Reports
    • View Item
    •   SMARTech Home
    • College of Computing (CoC)
    • College of Computing Technical Reports
    • View Item
    JavaScript is disabled for your browser. Some features of this site may not work without it.

    GCDX of p-1,q-1 for Random p,q

    Thumbnail
    View/Open
    GIT-CC-03-52.pdf (101.3Kb)
    Date
    2003
    Author
    Vishnoi, Nisheeth Kumar
    Metadata
    Show full item record
    Abstract
    In this note we study the following problem: How big can the greatest common divisor of p−1 and q−1 be, where p, q are randomly chosen primes in the set {1, . . . ,N}? Apart from being of independent interest, this problem arises in security when one wants to use an l (= 1024) bit RSA crypto coprocessor to do 2l bit cryptography [3]. One can answer this question quickly if one is allowed asymptotic results. But in practice one has N = 2[superscript 1024], so asymptotic results do not make much sense. It was observed that with probability at least than 0.99 ([3]), the g.c.d. is less than 32 bit. In this note we prove exactly this! To do so we combine some non-trivial exact results from analytic number theory.
    URI
    http://hdl.handle.net/1853/6512
    Collections
    • College of Computing Technical Reports [506]

    Browse

    All of SMARTechCommunities & CollectionsDatesAuthorsTitlesSubjectsTypesThis CollectionDatesAuthorsTitlesSubjectsTypes

    My SMARTech

    Login

    Statistics

    View Usage StatisticsView Google Analytics Statistics
    facebook instagram twitter youtube
    • My Account
    • Contact us
    • Directory
    • Campus Map
    • Support/Give
    • Library Accessibility
      • About SMARTech
      • SMARTech Terms of Use
    Georgia Tech Library266 4th Street NW, Atlanta, GA 30332
    404.894.4500
    • Emergency Information
    • Legal and Privacy Information
    • Human Trafficking Notice
    • Accessibility
    • Accountability
    • Accreditation
    • Employment
    © 2020 Georgia Institute of Technology