Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

quotient of Multivariate polynomial over Finite Fields by ideal not working as expected, same univariate costructions not affected #39246

Open
2 tasks done
dhalsimax opened this issue Jan 3, 2025 · 0 comments
Labels

Comments

@dhalsimax
Copy link

dhalsimax commented Jan 3, 2025

Steps To Reproduce

I'm trying to understand schoof algorithm with sage implementation here https://cocalc.com/share/public_paths/600832aafc89f1098d5415b39eec4fbaa63ccab1
I've done a conversion of the above as this:
schoof_multivar.sage.txt

Expected Behavior

Working with big primes , exact computation of the endomorphisms for all traces ell

Actual Behavior

Workign well with small primes and small primes powers as big as 256 bits, Not working for big primes example p=2650038686143, errors was:

line 19, in add
m = (b2-b1)/(a2-a1)
~~~~~~~^^~~~~~~
File "sage/structure/element.pyx", line 1729, in sage.structure.element.Element.truediv (/var/tmp/portage/sci-mathematics/sagemath-standard-10.5/work/sagemath_standard-10.5-python3_12/build/cythonized/sage/structure/element.c:21260)
File "sage/structure/element.pyx", line 2758, in sage.structure.element.RingElement.div (/var/tmp/portage/sci-mathematics/sagemath-standard-10.5/work/sagemath_standard-10.5-python3_12/build/cythonized/sage/structure/element.c:29273)
File "/usr/lib/python3.12/site-packages/sage/rings/quotient_ring_element.py", line 449, in div
XY = L.lift((R,) + tuple(B))
^^^^^^^^^^^^^^^^^^^^^^^
File "/usr/lib/python3.12/site-packages/sage/rings/qqbar_decorators.py", line 98, in wrapper
return func(*args, **kwds)
^^^^^^^^^^^^^^^^^^^
File "/usr/lib/python3.12/site-packages/sage/rings/polynomial/multi_polynomial_element.py", line 2246, in lift
Is = I.singular()
^^^^^^^^^^^^
AttributeError: 'tuple' object has no attribute 'singular'

Moreovers for some "ell" values the computations seems not to work as excpected:

"""

Elliptic Curve defined by y^2 = x^3 + 5*x + 56 over Finite Field of size 1303
-47
1351

computing t mod 2...
Univariate Polynomial Ring in t over Finite Field of size 1303
t = 1 mod 2 computed in 0.00 secs
computing t mod 3...
computing tl...
constructing R/<h,E> quotient ring...
computing (x^q,y^q)...
computing (x^q^2,y^q^2)...
computing ql...
computing (x^q^2,y^q^2)+ql...
looking for (x^q^2,y^q^2)+ql = tl...
0...
1...
Sage not working as expected for ell=3, but this trik works...
t = 1 mod 3 computed in 0.01 secs
computing t mod 5...
computing tl...
constructing R/<h,E> quotient ring...
computing (x^q,y^q)...
computing (x^q^2,y^q^2)...
computing ql...
computing (x^q^2,y^q^2)+ql...
looking for (x^q^2,y^q^2)+ql = tl...
0...
1...
2...
3...
t = 3 mod 5 computed in 0.01 secs
computing t mod 7...
computing tl...
constructing R/<h,E> quotient ring...
computing (x^q,y^q)...
computing (x^q^2,y^q^2)...
computing ql...
computing (x^q^2,y^q^2)+ql...
looking for (x^q^2,y^q^2)+ql = tl...
0...
1...
2...
Sage not working as expected for ell=7, but this trik works...
t = 2 mod 7 computed in 0.01 secs
trace -47 computed in 0.05 secs
1351

"""

WORKARAUND:

Note the warning "Sage not working as expected for ell=7, but this trik works..."
The trick was to raise an arithmetic error adding two "real" opposite points but having different affine coordinates in the endomorphisms thus generating a zero divisor in the arithmetic. This should not happen as S and T should be guarrented to be equal at some point before

Additional Information

https://www.google.com/url?sa=t&source=web&rct=j&opi=89978449&url=https://math.mit.edu/classes/18.783/2022/LectureNotes8.pdf&ved=2ahUKEwiU_76wmdmKAxVY4AIHHS-eKIQQFnoECA4QAQ&usg=AOvVaw3GOLXTiomfsa-ilpgDN_Do

Environment

  • OS: Gentoo linux
  • Sage Version: Sage 10.5

Checklist

  • I have searched the existing issues for a bug report that matches the one I want to file, without success.
  • I have read the documentation and troubleshoot guide
@dhalsimax dhalsimax changed the title <title>quotient of Multivariate polynomial over Finite Fields by ideal not working as expected, same univariate costructions not affected quotient of Multivariate polynomial over Finite Fields by ideal not working as expected, same univariate costructions not affected Jan 3, 2025
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
Projects
None yet
Development

No branches or pull requests

1 participant