n-WN
commented
2 months ago 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
culler
Ubuntu--SageMath 9.0 with 4G memory can be executed correctly (about 7 minutes) with default settings (sage stack size not modified)
Ubuntu
Output(Ubuntu):
macOS