commons-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Gilles Sadowski <>
Subject Re: [math] integer factorization
Date Tue, 07 Aug 2012 10:48:17 GMT

> > However do you have a concrete use-case for this feature?
> > What
> about an implementation with "BigInteger"? I'd guess that would make >
> the feature more apt to be used in "real" applications (just
> guessing).
> Well I have to admit that my current use case is fairly
> exotic: testing whether an irreducible polynomial in Zp(x) is primitive
> or not (p being a prime, I need the prime factors of (p^m)-1.
> In this
> context, the int type is enough.
> A less exotic use case is about
> arranging stuff: for example when one wants to arrange a given number N
> of small boxes in a bigger boxes. Given the prime factors of N, one can
> enumerate the possible sizes of the bigger boxes. 
> In other applications
> of prime numbers, it is usually not the prime factors that are needed
> but a primality test.
> I also have this functionality for the int type
> (using Miller-Rabin in such a way that the result is deterministic
> rather than probabilistic).
> It is true that for random bit generation
> int or even long would not be enough.
> For hash tables, the int range
> seems decent (I don't really know this use case).
> I proposed to
> restrict to int type just because this is what I have now. This can be a
> first step and then we can consider BigInteger...
> > Maybe we can add it
> in "ArithmeticUtils".
> int code is less than 500 lines so it could be
> added to on the other hand, an implementation
> dealing with BigInteger is bound to be much bigger. The ECC
> implementation of Dario Alejandro Alpern (see
> is about 7000 lines after removing
> the applet stuff. You probably don't want this to be added to

Following this explanation, I'm inclined to agree to extend the CM feature

Given the potential for extension, this should definitely not go in
"ArithmeticUtils" but in a package of its own.
Suggestions on how to lay out the structure?


To unsubscribe, e-mail:
For additional commands, e-mail:

View raw message