Ask Your Question

Revision history [back]

click to hide/show revision 1
initial version

Where does sagemath's speed in calculating gcd come from?

Hey, I was wondering how can sagemath can calculate gcds without calculating the numbers at stake? For instance,

sage: from Crypto.Util.number import long_to_bytes, inverse, bytes_to_long
sage: from Crypto.Hash import SHA256
sage: e = 65537
sage: gcd(bytes_to_long(SHA256.new(data=b'first').digest())^e-35211653423, bytes_to_long(SHA256.new(data=b'second').digest())^e-156535482153)

is computed nearly instantly while it will take forever for sage to calculate bytes_to_long(SHA256.new(data=b'first').digest())^e.

Is it perhaps part of symbolic computation?

Thanks :)