Modular exponentiation via the explicit Chinese remainder theorem

D.J. Bernstein, J.P. Sorenson

    Onderzoeksoutput: Bijdrage aan tijdschriftTijdschriftartikelAcademicpeer review

    14 Citaten (Scopus)
    2 Downloads (Pure)


    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.
    Originele taal-2Engels
    Pagina's (van-tot)443-454
    TijdschriftMathematics of Computation
    StatusGepubliceerd - 2007


    Duik in de onderzoeksthema's van 'Modular exponentiation via the explicit Chinese remainder theorem'. Samen vormen ze een unieke vingerafdruk.

    Citeer dit