Open n-WN opened 3 months ago
what is Crypto.Util.number
?
what is
Crypto.Util.number
?
perhaps it's just incompatibility with the current Sage version
do you get the correct root count if you skip all that Crypto stuff?
in the "expected behaviour" section you don't import * from that thing, you only import one function
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
in the "expected behaviour" section you don't import * from that thing, you only import one function
I will revise it.
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:
could it be just a Pari/GP bug? Can you reproduce without Sage?
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)
.
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 thePariError
.)I got the errors with
pari.allocatemem(20000000000)
but not withpari.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
Steps To Reproduce
Expected Behavior
Ubuntu
Output(Ubuntu):
Actual Behavior
I compiled sage myself on my ArchLinux Arm, and
nth_root()
also had problemsAdditional Information
No response
Environment