6 ms·

I believe all this functionality is already within sage, except for the Solovay-Strassen primality test.

• Labo333 9y ago
  I don't think Sage has the Jacobi symbol (just the Legendre), but Jacobi and Solovay-Strassen are less than 20 lines. Anyway, the goal was to provide very simple and readable implementations. Sage is far more powerful. Also, I think Sage uses square free factorisation algorithms that run much faster than Berlekamp. Anyway, we had much fun coding that and I really didn't expect to receive so many uovotes!
  • mixedmath 9y ago
    No, it's good work. Sage is hard to read, and your code is easy to read. Good job!
    • Labo333 9y ago
      Thanks a lot :)
    • williamstein 9y ago
      Indeed, Sage can be difficult to read, because our primary motivation is speed and scalable to support cutting edge research. If you don't know about it, you might find https://pypi.python.org/pypi/NZMATH https://pypi.python.org/pypi/NZMATH useful; it's BSD-licensed pure python number theory code.
  • williamstein 9y ago
    (I'm the guy who started Sage.) Sage has the Jacobi symbol as of 7 years ago (see https://trac.sagemath.org/ticket/11138 https://trac.sagemath.org/ticket/11138 and https://github.com/sagemath/sage/blob/07d6c37d18811e2b377a9689790a7c5e24da16ba/src/sage/arith/misc.py#L3426 https://github.com/sagemath/sage/blob/07d6c37d18811e2b377a96...). Sage is pretty good at primality testing, because PARI is. I'm really glad that the author of this library is enjoying writing Algebraic number theory that is readable and in Python3. Go for it, and have fun!