2018-11-12 08:23:15 -0500 received badge ● Popular Question (source) 2018-03-01 10:35:14 -0500 received badge ● Notable Question (source) 2018-03-01 10:35:14 -0500 received badge ● Popular Question (source) 2017-02-06 08:59:35 -0500 asked a question Trying to understand a Univariate Quotient Polynomial Ring over Finite Field This might be a silly question and I am sorry for my lack of knowledge in abstract algebra. I am trying to understand a Univariate Quotient Polynomial Ring over Finite Field but I want to make sure I am correct. So, if we have a polynomial, for example: $p = c_1 + c_2x^1 + c_3x^2 + \dots \ c_nx^{n-1}$ where $c_{i} \in \mathbb{Z}$. Now to bring this polynomial into Quotient Polynomial Ring over Finite Field, for example: $r = x^{1024} + 1$ as a irreducible polynomial and some prime $q$ as a modulus. First we need to find a quotient of division of $p / r$ and then for every coefficient in $p$ we need to $\bmod q$. Am I right? or completely off track? I just want to know how SageMath does something like this: modulus = 12289 # some prime R. = PolynomialRing(GF(modulus)) Y. = R.quotient(X^(1024) + 1) The reason I am asking this question is because I wrote something like this to simulate above SageMath code but it returns false: import random from itertools import izip from math import fabs dimension = 25 # degree of polynomials modulus = 40961 # modulus # ring = x^dimension + 1 ring =  + [0 for _ in range(dimension - 1)] +  # Quotient polynomial ring R. = PolynomialRing(GF(modulus)) # Gaussian field of integers Y. = R.quotient(X^(dimension) + 1) # Cyclotomic field def division(N, D): dD = degree(D) dN = degree(N) if dD < 0: raise ZeroDivisionError if dN >= dD: q =  * dN while dN >= dD: d =  * (dN - dD) + D mult = q[dN - dD] = N[-1] / d[-1] d = [coeff * mult for coeff in d] N = [abs(coeffN - coeffd) for coeffN, coeffd in izip(N, d)] dN = degree(N) r = N else: q =  r = N return (q, r) def degree(poly): while poly and poly[-1] == 0: poly.pop() # normalize return len(poly) - 1 def gen(): return [random.randint(100, 200) for _ in range(2^11)] def ring_correct(poly, irreduciblePoly, modulus): poly = division(poly, irreduciblePoly) poly = map(lambda x: x % modulus, poly) return poly T. = PolynomialRing(ZZ, 'x') a = gen() print Y(a).list() == T(ring_correct(a, ring, modulus)).list() Thanks in advance. 2016-10-31 19:27:10 -0500 received badge ● Scholar (source) 2016-10-31 19:27:05 -0500 received badge ● Supporter (source) 2016-10-31 19:24:17 -0500 received badge ● Notable Question (source) 2016-10-27 12:16:11 -0500 received badge ● Nice Question (source) 2016-10-27 10:50:35 -0500 received badge ● Student (source) 2016-10-27 09:48:24 -0500 received badge ● Popular Question (source) 2016-10-22 02:51:01 -0500 commented question Polynomial ring modulus integer to univariate polynomial ring over the Integers Link of the library (I didn't have sufficient points to have URL in my question): http://doc.sagemath.org/html/en/reference/stats/sage/stats/distributions/discrete_gaussian_polynomial.html#sage.stats.distributions.discrete_gaussian_polynomial.DiscreteGaussianDistributionPolynomialSampler.__init__ (link) 2016-10-22 02:50:00 -0500 asked a question Polynomial ring modulus integer to univariate polynomial ring over the Integers I want to use the DiscreteGaussianDistributionPolynomialSampler library: from sage.stats.distributions.discrete_gaussian_polynomial import DiscreteGaussianDistributionPolynomialSampler sage: DiscreteGaussianDistributionPolynomialSampler(ZZ['x'], 8, 3.0)() 3*x^7 + 3*x^6 - 3*x^5 - x^4 - 5*x^2 + 3 DiscreteGaussianDistributionPolynomialSampler(P, n, sigma) P - a univariate polynomial ring over the Integers n - number of coefficients to be sampled sigma - However, it takes a univariate polynomial ring over the Integers but I want to use a quotient ring of integers modulus instead. Something like this: Quotient polynomial ring of: (x^1024 + 1) modulus 13: modulus = 13 R = PolynomialRing(GF(modulus), "X") X = R.gen() Y = R.quotient(X^1024 + 1, "x") x = Y.gen() Question: Is it possible? if it is not possible is there a way to manually mod the result with x^1024 +1 and then with 13 afterwards? Any help would be appreciated. 2016-06-11 11:35:17 -0500 received badge ● Editor (source) 2016-06-11 11:33:48 -0500 commented question Trying to understand sage number system for BigInteger I don't have enough points to add links to my question. 2016-06-11 11:33:22 -0500 commented question Trying to understand sage number system for BigInteger link 1: http://stackoverflow.com/questions/37760255/trying-to-understand-sage-number-system-for-biginteger (http://stackoverflow.com/questions/37...) link 2: http://www.sagemath.org/ link 3: https://docs.oracle.com/javase/7/docs/api/java/math/BigInteger.html (https://docs.oracle.com/javase/7/docs...) link 4: http://stackoverflow.com/questions/11848887/bigdecimal-to-the-power-of-bigdecimal-on-java-android/22556217#22556217 (http://stackoverflow.com/questions/11...) link 5: http://www.apfloat.org/apfloat_java/ link 6: http://stackoverflow.com/a/16593009/1834787 (http://stackoverflow.com/a/16593009/1...) 2016-06-11 11:33:14 -0500 asked a question Trying to understand sage number system for BigInteger Note: I asked this question on Stackoverflow but it didn't get as much attention as it deserved. I thought asking it here might be a better approach. Thank you in advance. I have the following sage code that runs instantly (less than a second) and I am trying to convert it to Java (using Java's built-in BigInteger library). But I am not successful. In short, I initialized N as a BigInteger and delta as double and in order to calculate power (BigInteger ^ double) I converted N to BigDecimal (i.e. new BigDecimal(BigInteger)) and then: I used this approach but it is too slow (extremely slow). I used this library but I lost too much precision. I used this library but I got overflow exception. N = 16260595201356777876687102055392856230368799478725437225418970788404092751540966827614883675066492383688147288741223234174448378892794567789551235835087027626536919406320142455677084743499141155821894102610573207343199194327005172833989486958434982393556326206485954223151805798621294965926069728816780985683043030371485847746616146554612001066554175545753760388987584593091716701780398711910886679925612838955858736102229719042291682456480437908426849734556856917891628730543729446245974891735371991588505429152639045721840213451875487038496578525189542369448895368117152818687795094021869963915318643663536132393791 delta = 0.26 X = 2*floor(N^delta) # in sage, ^ operator means exponentiation # similar to ** operator in python print("X:" + str(x)) Output: X:32803899270297070621193977210731234596426011189989730481205367370572340252530823123935195892838208219967066426399488721710159859316222019683979411877007525412864 What is the magic? How sage does this? How to convert this code to Java (and be able to get a similar result), there should be some solution. 2016-05-02 03:46:43 -0500 asked a question Type error in sage: long is too large to convert to float I am new in sage and I have been trying for hours to fix the type issue. I used every possible data type in Python (e.g. Decimal, long and etc.) but no luck. I don't want to introduce a new data type in code. It would be great if the error could be fixed and X and Y be long a data type. Thank you so much in Advance. Code: N = long( '16260595201356777876687102055392856230368799478725437225418970788404092751540966827614883675066492383688147288741223234174448378892794567789551235835087027626536919406320142455677084743499141155821894102610573207343199194327005172833989486958434982393556326206485954223151805798621294965926069728816780985683043030371485847746616146554612001066554175545753760388987584593091716701780398711910886679925612838955858736102229719042291682456480437908426849734556856917891628730543729446245974891735371991588505429152639045721840213451875487038496578525189542369448895368117152818687795094021869963915318643663536132393791') e = long( '9278586176415637407263159408578691920359333372454377369719770617047980280946772628715887544861771332603998512490412112310956902919491486170574088276198189495386333836465063768828129359301433517440718437381660454785705721525097974857636068871096713768626273297901238473071056637845492072479070936932798180576585796558683754435768607883046039584737510259185971806751698550158026249176801507619064529443818304150648599396688870660401080227889827572469510021064725085334872793878678034795523371228947902585424135292996464136649558065449053206564552616679643325831942423442776280981153068472730957010986456115236454025653') delta = float(0.26) m = 4 t = int((1 - 2 * delta) * m) X = 2 * floor(N ^ delta) Y = floor(N ^ (1 / 2)) Error: Traceback (most recent call last): File "RSA/boneh_durfee.sage.py", line 306, in X = _sage_const_2 * floor(N ** delta) # this _might_ be too much OverflowError: long int too large to convert to float