Biography:

One of their most recent publications is Regular ArticlePolylog Depth Circuits for Integer Factoring and Discrete Logarithms. Which was published in journal Information and Computation.

More information about J. Sorenson research including statistics on their citations can be found on their Copernicus Academic profile page.

J. Sorenson's Articles: (1)

Regular ArticlePolylog Depth Circuits for Integer Factoring and Discrete Logarithms

AbstractIn this paper, we develop parallel algorithms for integer factoring and for computing discrete logarithms. In particular, we give polylog depth probabilistic boolean circuits of subexponential size for both of these problems, thereby solving an open problem of Adleman and Kompella. Existing sequential algorithms for integer factoring and discrete logarithms use a prime base which is the set of all primes up to a bound B. We use a much smaller value for B for our parallel algorithms than is typical for sequential algorithms. In particular, for inputs of length n, by setting B = nlogdn with d a positive constant, we construct •Probabilistic boolean circuits of depth (log) and size exp[(/log)] for completely factoring a positive integer with probability 1−(1), and•Probabilistic boolean circuits of depth (log + log) and size exp[(/log)] for computing discrete logarithms in the finite field () for a prime with probability 1−(1). These are the first results of this type for both problems.

Advertisement
Join Copernicus Academic and get access to over 12 million papers authored by 7+ million academics.
Join for free!

Contact us