Modular exponentiation via the explicit Chinese remainder theorem

D.J. Bernstein, J.P. Sorenson

    Research output: Contribution to journalArticlepeer-review

    12 Citations (Scopus)
    2 Downloads (Pure)

    Abstract

    Fix pairwise coprime positive integers . We propose representing integers modulo , where is any positive integer up to roughly , as vectors . We use this representation to obtain a new result on the parallel complexity of modular exponentiation: there is an algorithm for the Common CRCW PRAM that, given positive integers , , and in binary, of total bit length , computes in time using processors. For comparison, a parallelization of the standard binary algorithm takes superlinear time; Adleman and Kompella gave an expected time algorithm using processors; von zur Gathen gave an NC algorithm for the highly special case that is polynomially smooth.
    Original languageEnglish
    Pages (from-to)443-454
    JournalMathematics of Computation
    Volume76
    DOIs
    Publication statusPublished - 2007

    Fingerprint

    Dive into the research topics of 'Modular exponentiation via the explicit Chinese remainder theorem'. Together they form a unique fingerprint.

    Cite this