commons-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Phil Steitz <phil.ste...@gmail.com>
Subject Re: [math] integer factorization
Date Sun, 12 Aug 2012 20:03:49 GMT
On 8/7/12 3:48 AM, Gilles Sadowski wrote:
> 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?

Interesting question.  Logically, at the top level it should
probably be "number theory" or "algebra" but the first does not make
a good package name and I am not sure we will go very far in either
of these directions.  It might be OK to start just by adding methods
to ArithmeticUtils and see if we get a lot of interest / development
beyond just the simple methods being discussed here. If we do, we
can add an algebra.number or crypto (if that is where things head)
package in 4.0 and move implementations into an appropriate class in
the new package.

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


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


Mime
View raw message