ENT icon indicating copy to clipboard operation
ENT copied to clipboard

Faster operations needed

Open JASory opened this issue 4 years ago • 0 comments

Number-Theory's end goal is to be among the pre-eminent elementary number theory libraries of any language

While it is quite fast for machine-sized words (possibly the fastest in any language). It slacks in arbitrary precision arithmetic, with exponentiation in particular being about 60% slower than num-bigint.

In order of priority

  1. Faster exponentiation. Look into preallocation.
  2. Specialized Squaring operation
  3. Faster euclidean division, possibly recursive division
  4. Fast base-2 strong Fermat check
  5. Faster factorization needed, either in the form of elliptic curve factorization and/or quadratic sieve. Eventually the GNFS is planned to be implemented.
  6. Schonhage-Strassen multiplication using Fermat Transforms

JASory avatar Jan 14 '22 20:01 JASory