 CoCalc Public Files2017-06-29-105707.sagews
Author: Zhicong Huang
Views : 25
n = 2048; d = 16; r = 1
for i in range(1, 1000):
p = random_prime(2^16 - 1, False,  3)
if Zmod(2*n)(p).multiplicative_order() == d:
print 'p = ', p
if r > 1:
Q = Qp(p, prec = r + 1)
f = (Q[x])(x^n + 1).factor();
newf = Zmod(p**r)[x](f); newf
elif r == 1:
f = Zmod(p)[x](x^n+1).factor(); f

p = 60161 x^16 + 1500 p = 25343 x^16 + 43*x^8 + 25342 p = 36097 x^16 + 20 p = 9473 x^16 + 88 p = 60161 x^16 + 1500 p = 49919 x^16 + 126*x^8 + 49918 p = 36607 x^16 + 105*x^8 + 36606
n = 2048; d = 16; r = 1
for p in primes(3, 2^16 - 1):
if Zmod(2*n)(p).multiplicative_order() == d:
print 'p = ', p
if r > 1:
Q = Qp(p, prec = r + 1)
f = (Q[x])(x^n + 1).factor();
newf = Zmod(p**r)[x](f); newf
elif r == 1:
f = Zmod(p)[x](x^n+1).factor(); f

p = 257 x^16 + 3 p = 769 x^16 + 7 p = 1279 x^16 + 20*x^8 + 1278 p = 3329 x^16 + 17 p = 6911 x^16 + 36*x^8 + 6910 p = 7937 x^16 + 71 p = 8447 x^16 + 145*x^8 + 8446 p = 9473 x^16 + 88 p = 11519 x^16 + 70*x^8 + 11518 p = 13567 x^16 + 169*x^8 + 13566 p = 14081 x^16 + 26 p = 14591 x^16 + 90*x^8 + 14590 p = 14593 x^16 + 141 p = 16127 x^16 + 203*x^8 + 16126 p = 21247 x^16 + 135*x^8 + 21246 p = 22271 x^16 + 51*x^8 + 22270 p = 22273 x^16 + 281 p = 22783 x^16 + 351*x^8 + 22782 p = 23297 x^16 + 43 p = 25343 x^16 + 43*x^8 + 25342 p = 26879 x^16 + 277*x^8 + 26878 p = 26881 x^16 + 412 p = 28927 x^16 + 168*x^8 + 28926 p = 30977 x^16 + 430 p = 31489 x^16 + 296 p = 33023 x^16 + 323*x^8 + 33022 p = 36097 x^16 + 20 p = 36607 x^16 + 105*x^8 + 36606 p = 37633 x^16 + 178 p = 39679 x^16 + 268*x^8 + 39678 p = 40193 x^16 + 1018 p = 41729 x^16 + 89 p = 42239 x^16 + 1382*x^8 + 42238 p = 42751 x^16 + 118*x^8 + 42750 p = 43777 x^16 + 403 p = 45823 x^16 + 319*x^8 + 45822 p = 46337 x^16 + 208 p = 48383 x^16 + 282*x^8 + 48382 p = 49409 x^16 + 914 p = 49919 x^16 + 126*x^8 + 49918 p = 49921 x^16 + 373 p = 53503 x^16 + 293*x^8 + 53502 p = 57089 x^16 + 192 p = 57601 x^16 + 68 p = 58111 x^16 + 260*x^8 + 58110 p = 60161 x^16 + 1500 p = 62207 x^16 + 76*x^8 + 62206 p = 63743 x^16 + 628*x^8 + 63742
n = 128; d = 4; r = 1
for p in primes(3, 2^8 - 1):
if Zmod(2*n)(p).multiplicative_order() == d:
print 'p = ', p
f = Zmod(p)[x](x^n+1).factor(); f

p = 191 (x^4 + 5*x^2 + 190) * (x^4 + 12*x^2 + 190) * (x^4 + 18*x^2 + 190) * (x^4 + 22*x^2 + 190) * (x^4 + 32*x^2 + 190) * (x^4 + 35*x^2 + 190) * (x^4 + 38*x^2 + 190) * (x^4 + 40*x^2 + 190) * (x^4 + 45*x^2 + 190) * (x^4 + 47*x^2 + 190) * (x^4 + 51*x^2 + 190) * (x^4 + 56*x^2 + 190) * (x^4 + 59*x^2 + 190) * (x^4 + 60*x^2 + 190) * (x^4 + 64*x^2 + 190) * (x^4 + 93*x^2 + 190) * (x^4 + 98*x^2 + 190) * (x^4 + 127*x^2 + 190) * (x^4 + 131*x^2 + 190) * (x^4 + 132*x^2 + 190) * (x^4 + 135*x^2 + 190) * (x^4 + 140*x^2 + 190) * (x^4 + 144*x^2 + 190) * (x^4 + 146*x^2 + 190) * (x^4 + 151*x^2 + 190) * (x^4 + 153*x^2 + 190) * (x^4 + 156*x^2 + 190) * (x^4 + 159*x^2 + 190) * (x^4 + 169*x^2 + 190) * (x^4 + 173*x^2 + 190) * (x^4 + 179*x^2 + 190) * (x^4 + 186*x^2 + 190) p = 193 (x^4 + 11) * (x^4 + 13) * (x^4 + 20) * (x^4 + 29) * (x^4 + 33) * (x^4 + 35) * (x^4 + 39) * (x^4 + 60) * (x^4 + 68) * (x^4 + 71) * (x^4 + 74) * (x^4 + 76) * (x^4 + 87) * (x^4 + 88) * (x^4 + 89) * (x^4 + 94) * (x^4 + 99) * (x^4 + 104) * (x^4 + 105) * (x^4 + 106) * (x^4 + 117) * (x^4 + 119) * (x^4 + 122) * (x^4 + 125) * (x^4 + 133) * (x^4 + 154) * (x^4 + 158) * (x^4 + 160) * (x^4 + 164) * (x^4 + 173) * (x^4 + 180) * (x^4 + 182)

n = 8192; d = 16; r = 1
for p in primes(3, 2^24 - 1):
if Zmod(2*n)(p).multiplicative_order() == d:
print 'p = ', p
f = Zmod(p)[x](x^n+1).factor(); f

p = 5119 x^16 + 7*x^8 + 5118 p = 13313 x^16 + 7 p = 15359 x^16 + 5*x^8 + 15358 p = 15361 x^16 + 84 p = 19457 x^16 + 5 p = 21503 x^16 + x^8 + 21502 p = 25601 x^16 + 31 p = 27647 x^16 + 44*x^8 + 27646 p = 33791 x^16 + 26*x^8 + 33790 p = 35839 x^16 + 129*x^8 + 35838 p = 37889 x^16 + 95 p = 39937 x^16 + 143 p = 41983 x^16 + 62*x^8 + 41982 p = 50177 x^16 + 35 p = 52223 x^16 + 174*x^8 + 52222 p = 58367 x^16 + 260*x^8 + 58366 p = 58369 x^16 + 29 p = 64513 x^16 + 156 p = 70657 x^16 + 53 p = 76801 x^16 + 231 p = 80897 x^16 + 6 p = 84991 x^16 + 203*x^8 + 84990 p = 87041 x^16 + 30 p = 89087 x^16 + 359*x^8 + 89086 p = 95231 x^16 + 3*x^8 + 95230 p = 95233
Error in lines 2-5 Traceback (most recent call last): File "/cocalc/lib/python2.7/site-packages/smc_sagews/sage_server.py", line 1234, in execute flags=compile_flags), namespace, locals) File "", line 4, in <module> File "sage/rings/polynomial/polynomial_zmod_flint.pyx", line 742, in sage.rings.polynomial.polynomial_zmod_flint.Polynomial_zmod_flint.factor (build/cythonized/sage/rings/polynomial/polynomial_zmod_flint.cpp:18685) return factor_helper(self) File "./sage/libs/flint/nmod_poly_linkage.pxi", line 653, in sage.rings.polynomial.polynomial_zmod_flint.factor_helper (build/cythonized/sage/rings/polynomial/polynomial_zmod_flint.cpp:6013) return Factorization(factor_list, unit=poly.leading_coefficient(), File "sage/rings/polynomial/polynomial_element.pyx", line 5444, in sage.rings.polynomial.polynomial_element.Polynomial.leading_coefficient (build/cythonized/sage/rings/polynomial/polynomial_element.c:44451) return self[self.degree()] File "sage/rings/polynomial/polynomial_element.pyx", line 1112, in sage.rings.polynomial.polynomial_element.Polynomial.__getitem__ (build/cythonized/sage/rings/polynomial/polynomial_element.c:12377) return self.get_coeff_c(pyobject_to_long(n)) File "sage/rings/polynomial/polynomial_element.pyx", line 1120, in sage.rings.polynomial.polynomial_element.Polynomial.get_coeff_c (build/cythonized/sage/rings/polynomial/polynomial_element.c:12480) return self.get_unsafe(i) File "sage/rings/polynomial/polynomial_zmod_flint.pyx", line 264, in sage.rings.polynomial.polynomial_zmod_flint.Polynomial_zmod_flint.get_unsafe (build/cythonized/sage/rings/polynomial/polynomial_zmod_flint.cpp:15187) return self._parent.base_ring()(c) File "sage/structure/parent.pyx", line 896, in sage.structure.parent.Parent.__call__ (build/cythonized/sage/structure/parent.c:9133) mor = <map.Map> self._internal_convert_map_from(R) File "sage/structure/parent.pyx", line 2372, in sage.structure.parent.Parent._internal_convert_map_from (build/cythonized/sage/structure/parent.c:18755) mor = self.discover_convert_map_from(S) File "sage/structure/parent.pyx", line 2388, in sage.structure.parent.Parent.discover_convert_map_from (build/cythonized/sage/structure/parent.c:18948) cdef map.Map mor = self._internal_coerce_map_from(S) File "sage/structure/parent.pyx", line 2107, in sage.structure.parent.Parent._internal_coerce_map_from (build/cythonized/sage/structure/parent.c:16996) if S == self: File "sage/structure/richcmp.pyx", line 273, in sage.structure.richcmp.slot_tp_richcompare (build/cythonized/sage/structure/richcmp.c:1851) return self.__richcmp__(other, op) File "/ext/sage/sage-8.9_1804/local/lib/python2.7/site-packages/sage/rings/finite_rings/integer_mod_ring.py", line 1281, in __richcmp__ def __richcmp__(self, other, op): File "src/cysignals/signals.pyx", line 320, in cysignals.signals.python_check_interrupt KeyboardInterrupt