Node.js's profile - activity

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.<X> = PolynomialRing(GF(modulus))     
Y.<x> = 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 = [1] + [0 for _ in range(dimension - 1)] + [1]

# Quotient polynomial ring
R.<X> = PolynomialRing(GF(modulus))     # Gaussian field of integers
Y.<x> = 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 = [0] * dN
        while dN >= dD:
            d = [0] * (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 = [0]
        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)[0]

    poly = map(lambda x: x % modulus, poly)

    return poly

T.<t> = PolynomialRing(ZZ, 'x')

a = gen()

print Y(a).list() == T(ring_correct(a, ring, modulus)).list()

Thanks in advance.

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)

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.

I don't have enough points to add links to my question.

• 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...)

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:

1. I used this approach but it is too slow (extremely slow).
2. I used this library but I lost too much precision.
3. 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.

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 <module>
    X = _sage_const_2  * floor(N ** delta)  # this _might_ be too much OverflowError: long int too large to convert to float