commons-dev mailing list archives

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

> 
> > 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 ArithmeticUtils.java on the other hand, an implementation
> dealing with BigInteger is bound to be much bigger. The ECC
> implementation of Dario Alejandro Alpern (see
> http://www.alpertron.com.ar/ECM.HTM) is about 7000 lines after removing
> the applet stuff. You probably don't want this to be added to
> ArithmeticUtils.java...

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

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?


Regards,
Gilles

---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org
For additional commands, e-mail: dev-help@commons.apache.org


Mime
View raw message