sage archlinux ARM && macOS `nth_root()` have problems #38262

n-WN · 2024-06-23T04:26:58Z

Steps To Reproduce

ARM64 M1 macOS && Arch Linux ARM64

sage: pari.allocatemem(20000000000)
PARI stack size set to 20000000000 bytes, maximum size set to 20000014336
sage: from Crypto.Util.number import *
....:
....: p = 910274381122954393146066698371023619535913244728048515
....: 43344131406676387779969
....: n = 624973496337303421561014475892491063035627744701425827
....: 0888329547267471837899275103421406467763122499270790512099
....: 7028989398145479829316742472406230633347815295119735859775
....: 2226952270499737919467318170324778017914674949907229733487
....: 6619475914747479522310651303344623434565831770309615574478
....: 2744565490543324517734527731194530596184331602993190704302
....: 95124113199473337940505806777950838270849
....: e = 641747
....: c = 730024611795626517480532940587152891926416120514706825
....: 3684402303302599138377646328268840650655548394155400617523
....: 9714414056369827786441458456881269904887382055113118579685
....: 1863064509294123861487954267708318027370912496252338232193
....: 6194918603403958241801083358028130220665312320259973496837
....: 2535702425742009098132321729601948251607203678036551085555
....: 5146547481407283231721904830868033930943
....:
....: phi = p^4*(p-1)
....: Zmn = Zmod(p ** 5)
....: res = Zmn(c).nth_root(e, all=True)
....: for i in res:
....:     temp = long_to_bytes(int(i))
....:     if(b"flag" in temp):
....:         print(temp)
....:

Expected Behavior

Ubuntu

~/sage# uname -a
Linux test 5.4.0-153-generic #170-Ubuntu SMP Fri Jun 16 13:43:31 UTC 2023 x86_64 x86_64 x86_64 GNU/Linux

~/sage# cat qwb2023_not_only_RSA.sage
"""
~# sage
┌────────────────────────────────────────────────────────────────────┐
│ SageMath version 9.0, Release Date: 2020-01-01                     │
│ Using Python 3.8.10. Type "help()" for help.                       │
└────────────────────────────────────────────────────────────────────┘
sage:                               
"""
from sage.all import *
from Crypto.Util.number import long_to_bytes
from time import time

start = time()
p = 91027438112295439314606669837102361953591324472804851543344131406676387779969
n = 6249734963373034215610144758924910630356277447014258270888329547267471837899275103421406467763122499270790512099702898939814547982931674247240623063334781529511973585977522269522704997379194673181703247780179146749499072297334876619475914747479522310651303344623434565831770309615574478274456549054332451773452773119453059618433160299319070430295124113199473337940505806777950838270849
e = 641747
c = 730024611795626517480532940587152891926416120514706825368440230330259913837764632826884065065554839415540061752397144140563698277864414584568812699048873820551131185796851863064509294123861487954267708318027370912496252338232193619491860340395824180108335802813022066531232025997349683725357024257420090981323217296019482516072036780365510855555146547481407283231721904830868033930943

ZmodN = Zmod(p ** 5)
res = ZmodN(c).nth_root(e, all=True)
end = time()
print(f"Time: {end - start}")
print(f"Number of roots: {len(res)}")
for i in res:
    temp = long_to_bytes(int(i))
    if b"flag{" in temp:
        print(temp)
        break

Output(Ubuntu):

~# sage qwb2023_not_only_RSA.sage 
Time: 370.5116333961487
Number of roots: 641747
b"flag{c19c3ec0-d489-4bbb-83fc-bc0419a6822a}\x8e\xf5\x02-\xb5sAvQ9qX\xfb\xd9\x93U\x0b\x0b\xd9\x01\xe6e\xd3\x1d\x06\xd9V\x1bB\x1a\xed\xbb\xdf\xe8\x9b-\xb1\x8e\xd7\xcb\x0c@\x14\xbb:\xc9<\xe6tL\xa7\x04S\xad\xc1\x12 P\xcd\x9b.\xbdvK\t?|\xf5$\xf2\x8c\x989\xc4\x069\xb0\x10m\x0b\x96i\xaf\x14\x8d\x98,\xf6E\xc4{\x14\xe1-8mh{\x88\xe2\xec'\x92lz$\xb0)\xb6\xf6-u\x9b\xacS\x01"

Actual Behavior

ARM64 M1

....: res = Zmn(c).nth_root(e, all=True)
....: for i in res:
....:     temp = long_to_bytes(int(i))
....:     if(b"flag" in temp):
....:         print(temp)
....:
----------------------------------------------------------------
PariError                      Traceback (most recent call last)
File /private/var/tmp/sage-10.3-current/local/var/lib/sage/venv-python3.11.1/lib/python3.11/site-packages/sage/rings/polynomial/polynomial_element.pyx:5033, in sage.rings.polynomial.polynomial_element.Polynomial.factor (build/cythonized/sage/rings/polynomial/polynomial_element.c:52464)()
   5032 try:
-> 5033     G = list(self._pari_with_name().factor())
   5034 except PariError:

File cypari2/gen.pyx:4362, in cypari2.gen.Gen.factor()

File cypari2/handle_error.pyx:213, in cypari2.handle_error._pari_err_handle()

PariError: the PARI stack overflows (current size: 20000000000; maximum size: 20000014336)
You can use pari.allocatemem() to change the stack size and try again

During handling of the above exception, another exception occurred:

NotImplementedError            Traceback (most recent call last)
Cell In[10], line 10
      8 phi = p**Integer(4)*(p-Integer(1))
      9 Zmn = Zmod(p ** Integer(5))
---> 10 res = Zmn(c).nth_root(e, all=True)
     11 for i in res:
     12     temp = long_to_bytes(int(i))

File /private/var/tmp/sage-10.3-current/local/var/lib/sage/venv-python3.11.1/lib/python3.11/site-packages/sage/rings/finite_rings/integer_mod.pyx:1569, in sage.rings.finite_rings.integer_mod.IntegerMod_abstract.nth_root (build/cythonized/sage/rings/finite_rings/integer_mod.c:27231)()
   1567     modp = self % p
   1568     self = self / K(R.teichmuller(modp))
-> 1569     modp = modp.nth_root(n, all=all, algorithm=algorithm)
   1570 # now self is congruent to 1 mod 4 or 1 mod p (for odd p), so the power series for p-adic log converges.
   1571 # Hensel lifting is probably better, but this is easier at the moment.

File /private/var/tmp/sage-10.3-current/local/var/lib/sage/venv-python3.11.1/lib/python3.11/site-packages/sage/rings/finite_rings/integer_mod.pyx:1589, in sage.rings.finite_rings.integer_mod.IntegerMod_abstract.nth_root (build/cythonized/sage/rings/finite_rings/integer_mod.c:28264)()
   1587         else:
   1588             return sign[0] * K(R.teichmuller(modp) * (plog // n).exp())
-> 1589     return self._nth_root_common(n, all, algorithm, cunningham)
   1590
   1591 def _nth_root_naive(self, n):

File /private/var/tmp/sage-10.3-current/local/var/lib/sage/venv-python3.11.1/lib/python3.11/site-packages/sage/rings/finite_rings/element_base.pyx:134, in sage.rings.finite_rings.element_base.FiniteRingElement._nth_root_common (build/cythonized/sage/rings/finite_rings/element_base.c:6652)()
    132         self = self**x * gh**(-hinv*t)
    133 if all:
--> 134     nthroot = K.zeta(n)
    135     L = [self]
    136     for i in range(1,n):

File /private/var/tmp/sage-10.3-current/local/var/lib/sage/venv-python3.11.1/lib/python3.11/site-packages/sage/rings/ring.pyx:1021, in sage.rings.ring.Ring.zeta (build/cythonized/sage/rings/ring.c:11560)()
   1019 if all:
   1020     return [-P[0] for P, e in f.factor() if P.degree() == 1]
-> 1021 for P, e in f.factor():
   1022     if P.degree() == 1:
   1023         return -P[0]

File /private/var/tmp/sage-10.3-current/local/var/lib/sage/venv-python3.11.1/lib/python3.11/site-packages/sage/rings/polynomial/polynomial_element.pyx:5035, in sage.rings.polynomial.polynomial_element.Polynomial.factor (build/cythonized/sage/rings/polynomial/polynomial_element.c:52523)()
   5033         G = list(self._pari_with_name().factor())
   5034     except PariError:
-> 5035         raise NotImplementedError
   5036
   5037 elif isinstance(R, FiniteField):

NotImplementedError:
sage:

I compiled sage myself on my ArchLinux Arm, and nth_root() also had problems

~/s/sage> uname -a                                                                                                                                                                             develop!
Linux arch 6.9.3-orbstack-00146-g1a8d02c90788 #1 SMP Wed Jun 12 00:20:38 UTC 2024 aarch64 GNU/Linux

~/s/sage> ./sage                                                                                                                                                                               develop!
┌────────────────────────────────────────────────────────────────────┐
│ SageMath version 10.4.beta9, Release Date: 2024-06-09              │
│ Using Python 3.12.3. Type "help()" for help.                       │
└────────────────────────────────────────────────────────────────────┘
┏━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┓
┃ Warning: this is a prerelease version, and it may be unstable.     ┃
┗━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┛
sage: from sage.all import *
....: from Crypto.Util.number import long_to_bytes
....: from time import time
....:
....: start = time()
....: p = 91027438112295439314606669837102361953591324472804851543344131406676387779969
....: n = 62497349633730342156101447589249106303562774470142582708883295472674718378992751034214064677631224992707905120997028989398145479829316742472406230633347815295119735859775222695227049973791946731817032
....: 47780179146749499072297334876619475914747479522310651303344623434565831770309615574478274456549054332451773452773119453059618433160299319070430295124113199473337940505806777950838270849
....: e = 641747
....: c = 73002461179562651748053294058715289192641612051470682536844023033025991383776463282688406506555483941554006175239714414056369827786441458456881269904887382055113118579685186306450929412386148795426770
....: 8318027370912496252338232193619491860340395824180108335802813022066531232025997349683725357024257420090981323217296019482516072036780365510855555146547481407283231721904830868033930943
....:
....: ZmodN = Zmod(p ** 5)
....: res = ZmodN(c).nth_root(e, all=True)
....: end = time()
....: print(f"Time: {end - start}")
....: print(f"Number of roots: {len(res)}")
....: for i in res:
....:     temp = long_to_bytes(int(i))
....:     if b"flag{" in temp:
....:         print(temp)
....:         break
....:
---------------------------------------------------------------------------
PariError                                 Traceback (most recent call last)
File ~/sage/sage/src/sage/rings/polynomial/polynomial_element.pyx:5031, in sage.rings.polynomial.polynomial_element.Polynomial.factor()
   5030 try:
-> 5031     G = list(self._pari_with_name().factor())
   5032 except PariError:

File ~/sage/sageinstall/lib/python3.12/site-packages/cypari2/gen.pyx:4364, in cypari2.gen.Gen.factor()
   4363     factor_proven = 1 if proof else 0
-> 4364 sig_on()
   4365 if limit >= 0:

File ~/sage/sageinstall/lib/python3.12/site-packages/cypari2/handle_error.pyx:211, in cypari2.handle_error._pari_err_handle()
    210
--> 211     raise PariError(errnum, pari_error_string, clone_gen_noclear(E))
    212

PariError: the PARI stack overflows (current size: 1073741824; maximum size: 1073741824)
You can use pari.allocatemem() to change the stack size and try again

During handling of the above exception, another exception occurred:

NotImplementedError                       Traceback (most recent call last)
Cell In[1], line 12
      9 c = Integer(730024611795626517480532940587152891926416120514706825368440230330259913837764632826884065065554839415540061752397144140563698277864414584568812699048873820551131185796851863064509294123861487954267708318027370912496252338232193619491860340395824180108335802813022066531232025997349683725357024257420090981323217296019482516072036780365510855555146547481407283231721904830868033930943)
     11 ZmodN = Zmod(p ** Integer(5))
---> 12 res = ZmodN(c).nth_root(e, all=True)
     13 end = time()
     14 print(f"Time: {end - start}")

File ~/sage/sage/src/sage/rings/finite_rings/integer_mod.pyx:1570, in sage.rings.finite_rings.integer_mod.IntegerMod_abstract.nth_root()
   1568     modp = self % p
   1569     self = self / K(R.teichmuller(modp))
-> 1570     modp = modp.nth_root(n, all=all, algorithm=algorithm)
   1571 # now self is congruent to 1 mod 4 or 1 mod p (for odd p), so the power series for p-adic log converges.
   1572 # Hensel lifting is probably better, but this is easier at the moment.

File ~/sage/sage/src/sage/rings/finite_rings/integer_mod.pyx:1590, in sage.rings.finite_rings.integer_mod.IntegerMod_abstract.nth_root()
   1588         else:
   1589             return sign[0] * K(R.teichmuller(modp) * (plog // n).exp())
-> 1590     return self._nth_root_common(n, all, algorithm, cunningham)
   1591
   1592 def _nth_root_naive(self, n):

File ~/sage/sage/src/sage/rings/finite_rings/element_base.pyx:134, in sage.rings.finite_rings.element_base.FiniteRingElement._nth_root_common()
    132         self = self**x * gh**(-hinv*t)
    133 if all:
--> 134     nthroot = K.zeta(n)
    135     L = [self]
    136     for i in range(1,n):

File ~/sage/sage/src/sage/rings/ring.pyx:897, in sage.rings.ring.Ring.zeta()
    895 if all:
    896     return [-P[0] for P, e in f.factor() if P.degree() == 1]
--> 897 for P, e in f.factor():
    898     if P.degree() == 1:
    899         return -P[0]

File ~/sage/sage/src/sage/rings/polynomial/polynomial_element.pyx:5033, in sage.rings.polynomial.polynomial_element.Polynomial.factor()
   5031         G = list(self._pari_with_name().factor())
   5032     except PariError:
-> 5033         raise NotImplementedError
   5034
   5035 elif isinstance(R, FiniteField):

NotImplementedError:
sage: exit

Additional Information

No response

Environment

- **OS**:macOS & Arch Linux
- **Sage Version**:10.3 & 10.4 beta


sage --version
SageMath version 10.3, Release Date: 2024-03-19


```shell
Darwin ABC.local 23.5.0 Darwin Kernel Version 23.5.0: Wed May  1 20:12:58 PDT 2024; root:xnu-10063.121.3~5/RELEASE_ARM64_T6000 arm64 arm Darwin



### Checklist

- [X] I have searched the existing issues for a bug report that matches the one I want to file, without success.
- [X] I have read the documentation and troubleshoot guide

The text was updated successfully, but these errors were encountered:

dimpase · 2024-06-23T09:45:30Z

what is Crypto.Util.number ?

n-WN · 2024-06-23T10:57:12Z

what is Crypto.Util.number ?

https://pypi.org/project/pycryptodome/

dimpase · 2024-06-23T11:34:53Z

perhaps it's just incompatibility with the current Sage version

dimpase · 2024-06-23T11:38:57Z

do you get the correct root count if you skip all that Crypto stuff?

dimpase · 2024-06-23T11:41:05Z

in the "expected behaviour" section you don't import * from that thing, you only import one function

n-WN · 2024-06-23T11:49:17Z

do you get the correct root count if you skip all that Crypto stuff?

No,The encrypted content is filtered after nthroot returns to the root

n-WN · 2024-06-23T11:49:57Z

in the "expected behaviour" section you don't import * from that thing, you only import one function

I will revise it.

n-WN · 2024-06-23T14:17:09Z

res = ZmodN(c).nth_root(e, all=True)

This error occurs when mod and root opening times reach a certain large, and to do finite field root opening, you need to add Zmod().

> sage
┌────────────────────────────────────────────────────────────────────┐
│ SageMath version 10.3, Release Date: 2024-03-19                    │
│ Using Python 3.11.1. Type "help()" for help.                       │
└────────────────────────────────────────────────────────────────────┘
sage: p = 910274381122954393146066698371023619535913244728048515
....: 43344131406676387779969
sage: n = 624973496337303421561014475892491063035627744701425827
....: 0888329547267471837899275103421406467763122499270790512099
....: 7028989398145479829316742472406230633347815295119735859775
....: 2226952270499737919467318170324778017914674949907229733487
....: 6619475914747479522310651303344623434565831770309615574478
....: 2744565490543324517734527731194530596184331602993190704302
....: 95124113199473337940505806777950838270849
sage: e = 641747
sage: c = 730024611795626517480532940587152891926416120514706825
....: 3684402303302599138377646328268840650655548394155400617523
....: 9714414056369827786441458456881269904887382055113118579685
....: 1863064509294123861487954267708318027370912496252338232193
....: 6194918603403958241801083358028130220665312320259973496837
....: 2535702425742009098132321729601948251607203678036551085555
....: 5146547481407283231721904830868033930943
sage: ZmodN = Zmod(p ** 5)
sage: res = ZmodN(c).nth_root(e, all=True)
----------------------------------------------------------------
PariError                      Traceback (most recent call last)
File /private/var/tmp/sage-10.3-current/local/var/lib/sage/venv-python3.11.1/lib/python3.11/site-packages/sage/rings/polynomial/polynomial_element.pyx:5033, in sage.rings.polynomial.polynomial_element.Polynomial.factor (build/cythonized/sage/rings/polynomial/polynomial_element.c:52464)()
   5032 try:
-> 5033     G = list(self._pari_with_name().factor())
   5034 except PariError:

File cypari2/gen.pyx:4362, in cypari2.gen.Gen.factor()

File cypari2/handle_error.pyx:213, in cypari2.handle_error._pari_err_handle()

PariError: the PARI stack overflows (current size: 1073741824; maximum size: 1073741824)
You can use pari.allocatemem() to change the stack size and try again

During handling of the above exception, another exception occurred:

NotImplementedError            Traceback (most recent call last)
Cell In[6], line 1
----> 1 res = ZmodN(c).nth_root(e, all=True)

File /private/var/tmp/sage-10.3-current/local/var/lib/sage/venv-python3.11.1/lib/python3.11/site-packages/sage/rings/finite_rings/integer_mod.pyx:1569, in sage.rings.finite_rings.integer_mod.IntegerMod_abstract.nth_root (build/cythonized/sage/rings/finite_rings/integer_mod.c:27231)()
   1567     modp = self % p
   1568     self = self / K(R.teichmuller(modp))
-> 1569     modp = modp.nth_root(n, all=all, algorithm=algorithm)
   1570 # now self is congruent to 1 mod 4 or 1 mod p (for odd p), so the power series for p-adic log converges.
   1571 # Hensel lifting is probably better, but this is easier at the moment.

File /private/var/tmp/sage-10.3-current/local/var/lib/sage/venv-python3.11.1/lib/python3.11/site-packages/sage/rings/finite_rings/integer_mod.pyx:1589, in sage.rings.finite_rings.integer_mod.IntegerMod_abstract.nth_root (build/cythonized/sage/rings/finite_rings/integer_mod.c:28264)()
   1587         else:
   1588             return sign[0] * K(R.teichmuller(modp) * (plog // n).exp())
-> 1589     return self._nth_root_common(n, all, algorithm, cunningham)
   1590
   1591 def _nth_root_naive(self, n):

File /private/var/tmp/sage-10.3-current/local/var/lib/sage/venv-python3.11.1/lib/python3.11/site-packages/sage/rings/finite_rings/element_base.pyx:134, in sage.rings.finite_rings.element_base.FiniteRingElement._nth_root_common (build/cythonized/sage/rings/finite_rings/element_base.c:6652)()
    132         self = self**x * gh**(-hinv*t)
    133 if all:
--> 134     nthroot = K.zeta(n)
    135     L = [self]
    136     for i in range(1,n):

File /private/var/tmp/sage-10.3-current/local/var/lib/sage/venv-python3.11.1/lib/python3.11/site-packages/sage/rings/ring.pyx:1021, in sage.rings.ring.Ring.zeta (build/cythonized/sage/rings/ring.c:11560)()
   1019 if all:
   1020     return [-P[0] for P, e in f.factor() if P.degree() == 1]
-> 1021 for P, e in f.factor():
   1022     if P.degree() == 1:
   1023         return -P[0]

File /private/var/tmp/sage-10.3-current/local/var/lib/sage/venv-python3.11.1/lib/python3.11/site-packages/sage/rings/polynomial/polynomial_element.pyx:5035, in sage.rings.polynomial.polynomial_element.Polynomial.factor (build/cythonized/sage/rings/polynomial/polynomial_element.c:52523)()
   5033         G = list(self._pari_with_name().factor())
   5034     except PariError:
-> 5035         raise NotImplementedError
   5036
   5037 elif isinstance(R, FiniteField):

NotImplementedError:
sage:

dimpase · 2024-06-23T18:58:36Z

could it be just a Pari/GP bug? Can you reproduce without Sage?

DaveWitteMorris · 2024-06-24T00:29:02Z

I don't think this is a sagemath bug. The problem is that pari runs out of memory -- note that the first error in the Traceback is:

PariError: the PARI stack overflows (current size: 1073741824; maximum size: 1073741824)
You can use pari.allocatemem() to change the stack size and try again

(The NotImplementedError is misleading and is raised as a result of the PariError.)

I got the errors with pari.allocatemem(20000000000) but not with pari.allocatemem(30000000000).

n-WN · 2024-06-24T04:15:09Z

I don't think this is a sagemath bug. The problem is that pari runs out of memory -- note that the first error in the Traceback is:
PariError: the PARI stack overflows (current size: 1073741824; maximum size: 1073741824)
You can use pari.allocatemem() to change the stack size and try again
(The NotImplementedError is misleading and is raised as a result of the PariError.)

I got the errors with pari.allocatemem(20000000000) but not with pari.allocatemem(30000000000).

It's possible, but I got normal output on Ubuntu with 4GB ram.

[√] Ubuntu with 4GB ram. sage 9.5 Results will be available in less than ten minutes
[x] macOS with 16GB ram. sage 10.3 After adjusting to pari.allocatemem(30000000000), no result appeared for twenty minutes, CPU: Apple M1 Pro
[x] archlinux ARM with 12GB ram. sage 10.4beta

n-WN added the t: bug label Jun 23, 2024

n-WN changed the title ~~<title> sage archlinux ARM && macOS nth_root() have problems~~ sage archlinux ARM && macOS nth_root() have problems Jun 24, 2024

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

sage archlinux ARM && macOS `nth_root()` have problems #38262

sage archlinux ARM && macOS `nth_root()` have problems #38262

n-WN commented Jun 23, 2024

dimpase commented Jun 23, 2024

n-WN commented Jun 23, 2024

dimpase commented Jun 23, 2024

dimpase commented Jun 23, 2024

dimpase commented Jun 23, 2024

n-WN commented Jun 23, 2024

n-WN commented Jun 23, 2024

n-WN commented Jun 23, 2024

dimpase commented Jun 23, 2024

DaveWitteMorris commented Jun 24, 2024

n-WN commented Jun 24, 2024 •

edited

Loading

sage archlinux ARM && macOS nth_root() have problems #38262

sage archlinux ARM && macOS nth_root() have problems #38262

Comments

n-WN commented Jun 23, 2024

Steps To Reproduce

Expected Behavior

Ubuntu

Output(Ubuntu):

Actual Behavior

Additional Information

Environment

dimpase commented Jun 23, 2024

n-WN commented Jun 23, 2024

dimpase commented Jun 23, 2024

dimpase commented Jun 23, 2024

dimpase commented Jun 23, 2024

n-WN commented Jun 23, 2024

n-WN commented Jun 23, 2024

n-WN commented Jun 23, 2024

dimpase commented Jun 23, 2024

DaveWitteMorris commented Jun 24, 2024

n-WN commented Jun 24, 2024 • edited Loading

sage archlinux ARM && macOS `nth_root()` have problems #38262

sage archlinux ARM && macOS `nth_root()` have problems #38262

n-WN commented Jun 24, 2024 •

edited

Loading