Revision history [back]

I am quite new to Sage, so sorry in advance if the question is silly. I have searched the web and found not much that would be related.

I am trying to implement an factorization algorithm using elliptic curves (homework assignment). Say we are trying to factorize some n. The key point in the algorithm is to draw some knowledge from an error in arithmetic on a curve modulo n. More precisely, the error arises when (and only when) we are trying to invert some element in the modulo arithmetic when it is not invertible - and it means that it is not coprime to n, and thus taking their gcd we can find a factor of n.

What I don't know is how to get to the data included in the error message from inside the program.

An example is as follows:

n = 51
K = 720
C = EllipticCurve(Integers(n), [2,49])
P = C([1,1])
try:
    K*P
except ZeroDivisionError:
    raise

In the above code an error arises when computing K*P, which is caught and then thrown once more (since I don't know what else to do with it). The error message says:

Traceback (click to the left of this block for traceback)
...
ZeroDivisionError: Inverse of 34 does not exist (characteristic = 51 =
17*3)

I would like to get my hands on the number 34 appearing in the error message, without actually breaking the computation, so that it can be used in the program.

Ideally, it would work somewhat like that:

n = 51
K = 720
C = EllipticCurve(Integers(n), [2,49])
P = C([1,1])
try:
    K*P
except ZeroDivisionError:
    d = some_magic_function()
    g = gcd(d,p)
    print p, 'has divisor', g

I would appreciate any hints as to how it can be done.

Disclaimer: I have mentioned the question being connected to homework. The assignment was however only to cause the error message to appear, an then copy-paste the interesting number and resume computation. I find this approach somewhat dirty and hoped to look for something neater. I believe I am not doing anything immoral here.

I am quite new to Sage, so sorry in advance if the question is silly. I have searched the web and found not much that would be related.

I am trying to implement an factorization algorithm using elliptic curves (homework assignment). Say we are trying to factorize some n. The key point in the algorithm is to draw some knowledge from an error in arithmetic on a curve modulo n. More precisely, the error arises when (and only when) we are trying to invert some element in the modulo arithmetic when it is not invertible - and it means that it is not coprime to n, and thus taking their gcd we can find a factor of n.

What I don't know is how to get to the data included in the error message from inside the program.

An example is as follows:

n = 51
K = 720
C = EllipticCurve(Integers(n), [2,49])
P = C([1,1])
try:
    K*P
except ZeroDivisionError:
    raise

In the above code an error arises when computing K*P, which is caught and then thrown once more (since I don't know what else to do with it). The error message says:

Traceback (click to the left of this block for traceback)
...
ZeroDivisionError: Inverse of 34 does not exist (characteristic = 51 =
17*3)

I would like to get my hands on the number 34 appearing in the error message, without actually breaking the computation, so that it can be used in the program.

Ideally, it would work somewhat like that:

n = 51
K = 720
C = EllipticCurve(Integers(n), [2,49])
P = C([1,1])
try:
    K*P
except ZeroDivisionError:
    d = some_magic_function()
    g = gcd(d,p)
gcd(d,n)
    print p, n, 'has divisor', g

I would appreciate any hints as to how it can be done.

Disclaimer: I have mentioned the question being connected to homework. The assignment was however only to cause the error message to appear, an then copy-paste the interesting number and resume computation. I find this approach somewhat dirty and hoped to look for something neater. I believe I am not doing anything immoral here.