Как исправить ошибку с функцией мод в Sagemath? - PullRequest
Новая
       12

Как исправить ошибку с функцией мод в Sagemath?

0 голосов
/ 27 февраля 2019

Я решил использовать Sagemath, потому что слышал, что он очень полезен в теории чисел.Я сделал эту программу (это моя первая программа) для разложения числа, и я не знаю, почему она не работает.Я думаю, что это связано с определенным свойством функции мода, но я не уверен.

Кто-нибудь знает, как это исправить?Спасибо. 

    #Pollard algorithm
k=87757
f(x)=x^2+1
x=1
y=x
iter=20
i=0
while(i<iter):
    i=i+1
    x=mod(f(x),k)
    y=mod(f(f(y)),k)
    g=(x-y).gcd(k)
    if(1<g and g<k):
        print(g)
        print(i)
        break

1 Ответ

0 голосов
/ 27 февраля 2019

Я считаю, что проблема действительно в том, что вы используете функцию mod.Как только вы делаете x = mod(f(x), k), тогда x живет в кольце Z/kZ.То же самое относится и к g.Неравенства в этом кольце на самом деле не имеют смысла, и, в частности, g<k будет переведено в g<0.Это связано с тем, что k=0 mod k и когда вы выполняете алгебраические операции, проверку на равенство, проверку на неравенство и т. Д., Обе стороны преобразуются в лучшее доступное кольцо.В этом случае это кольцо Z/kZ.

Вероятно, лучше работать с целыми числами все время: 

x = f(x).mod(k)
y = f(f(y)).mod(k)

Вот разница между использованием mod в качестве функцииили метод: 

sage: type(5.mod(3))  # method
<type 'sage.rings.integer.Integer'>
sage: type(mod(5, 3)) # function
<type 'sage.rings.finite_rings.integer_mod.IntegerMod_int'>

Если бы я хотел сохранить это в файле Python, подходящем для использования в Sage, я сделал бы это следующим образом: 

from sage.rings.all import Integer

def f(x):
    # Make sure to return a Sage Integer.
    return Integer(x**2+1)

def testing(iter=20):
    x=1
    y=x
    i=0
    k=87757
    while i<iter:
        i=i+1
        x=f(x).mod(k)
        y=f(f(y)).mod(k)
        g=(x-y).gcd(k)
        # For debugging:
        # print(x, y, g)
        if 1<g and g<k:
            print(g)
            print(i)
            break

Вы можете добавить дополнительные параметрык вашей функции: разрешите k в качестве ввода, x, y и т. д. В любом случае, затем выполните testing(20).

...