commons-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From matic <ma...@nimp.co.uk>
Subject Re: [math] integer factorization
Date Tue, 07 Aug 2012 08:24:29 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 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...

Sebastien

 
Mime
  • Unnamed multipart/alternative (inline, None, 0 bytes)
View raw message