Efficient BigInteger alternative for modular arithmetic

[GuutBoy]

For #316 we would like to implement a more efficient alternative to the BigInteger class when doing modular arithmetic.

We should consider an approach based on pseudo mersennes or Montegomery reduction or similar approaches.

We should also consider a mutable approach.

[mortendahl]

Any benchmark results to share? :)

[GuutBoy]

@mortendahl I do not have any concrete numbers. Last I heard from @pffrandsen who worked on this, using the the pseudo Mersenne prime approach saved something like 20% time when doing modular reductions compared to the generic method used in Java's BigInteger. However, the current implementation is not very heavily optimized, so there should be room for improvement over this.

[mortendahl]

Excellent, thanks!

[pffrandsen]

@ALL We did a number of benchmarks (using JDK8&9). It turned out that our data was stale. With JDK11, native java caught up with the alternative implementations. Meaning the original plan of substituting BigInteger with a custom implementation was no longer a good strategy. We then focused on pseudo Mersenne prime optimization, micro benchmarks suggest an improvement close to 20 %. It turned out that the framework was not ready for interchanging the modulus implementation (and not every prime is a psuedo Mersenne prime). The remainder of this (significant) change request was to implement an interchangeable modulus operation. We have a number of ideas and thoughts as a result of this change that we would like to test in a controlled test environment. We intent to work with an BigInteger implementation tailored to the MASCOT - this, however, will not happen in a couple of months. If you want to notified when we have completed a set of benchmarks and improvements, send me your email and I will include a specific update to you. Best Peter Morten Dahl wrote on 18-01-2019 11:00:

…

Excellent, thanks! — You are receiving this because you were mentioned. Reply to this email directly, view it on GitHub <#320 (comment)>, or mute the thread <https://github.com/notifications/unsubscribe-auth/AYAnFblUfjIgI1e--QIGf7oC7qbUm43Pks5vEZtXgaJpZM4Ydfqz>.

-- Peter F. Frandsen CTO SECATA email:pff@secata.com <mailto:pff@partisia.com> telephone:+45 3155 0064 <tel:+45%2031%2055%2000%2064>

[mortendahl]

Thanks for the details @pffrandsen, looking forward to further results! Will keep an eye on the repo but also happy to receive updates via mortendahlcs@gmail.com. Thank you.