Working with very large integers

asked 2013-12-05 17:23:35 -0500

this post is marked as community wiki

This post is a wiki. Anyone with karma >750 is welcome to improve it.

I would like to perform a fermat factorization on a number that is 600+ digits. Currently when I try to use that in sage I get "Python int too large to convert to C long." Is there an additional library or a specific sage function that I have to use in order to make this work?


edit retag flag offensive close merge delete


My guess is that your code somehow implicitly is using Python `int`s and not Sage `Integer`s. If you post (or link to) code, we can see where that happens and fix it. 600 digit integer factorization is not a problem for Sage.

kcrisman gravatar imagekcrisman ( 2013-12-06 03:48:36 -0500 )edit

"600 digit factorization is not a problem for Sage"?! I think that most 600-digit factorizations would be too hard.

John Cremona gravatar imageJohn Cremona ( 2013-12-11 05:47:23 -0500 )edit

I thought about what I must have meant, and what I must have meant was finding **a** factor, for most such integers. You are right that 600-digit numbers are not factoring nicely for me; I must have been too zealous! I thought that big crypto stuff wanted 1000-digit stuff now, but maybe it's 1000-bit... or maybe my expectations were too high.

kcrisman gravatar imagekcrisman ( 2013-12-11 15:51:28 -0500 )edit

That said, Fermat factorization should work okay (if it would work at all, of course) as long as one uses Sage `Integers` in custom-written code, shouldn't it?

kcrisman gravatar imagekcrisman ( 2013-12-11 15:52:05 -0500 )edit