mathutil icon indicating copy to clipboard operation
mathutil copied to clipboard

Published 20 hours ago • verified publisher icon cznic

FactorInt for big.Int ?

Open equal-l2 opened this issue 7 years ago • 3 comments

It would be great if FactorInt supports big.Int.

equal-l2 avatar Nov 05 '18 20:11 equal-l2

Which factoring algorithm it should implement? How should the API look like?

cznic avatar Nov 06 '18 19:11 cznic

I have no concrete idea, but we can't use the same algorithm as FactorInt(uint32)(trial division with precalculated primes) for big.Int, right?

equal-l2 avatar Nov 07 '18 01:11 equal-l2

I have no concrete idea, but we can't use the same algorithm as FactorInt(uint32)(trial division with precalculated primes) for big.Int, right?

Yes, that's definitely possible. What range of integers on input do you want to be able to factor using this approach?

cznic avatar Nov 07 '18 09:11 cznic