# Questions tagged as ['number-theory']

Number theory is the study of the properties and construction of numbers, particularly integers. Prime numbers are of particular interest to number theorists and consequently cryptographers as they are considered the "building blocks" of numbers and produce many interesting results which are useful in cryptography. Questions covering number theory and primes should use this tag; questions involving finite fields and groups might use this tag if relevant.
Score: 2
Sage code for finding generator matrix of MDS code
1. Let $$L$$ be an $$[n,k]$$ code. A $$k\times n$$ matrix $$G$$ whose rows form a basis for $$L$$ is called a generator matrix for $$L$$.

2. A linear $$[n,k,d]$$ code with largest possible minimum distance is called maximum distance $$d$$ separable or MDS code.

I want to find a generator matrix for MDS code using SageMath or in another way, is there any SageMath code to check a matrix is a generator matrix for the MDS ...

Score: 1
What are the expected values of a particular rotational-XOR property of a sequence of random bitstrings?

Assuming that $$x$$ is a sequence of $$l$$ bits and $$0 \le n < l$$, let $$R(x, n)$$ denote the result of the left bitwise rotation of $$x$$ by $$n$$ bits. For example, if $$x = 0100110001110000$$, then $$\begin{array}{l} R(x,0) = {\rm{0100110001110000}},\\ R(x,1) = {\rm{1001100011100000}},\\ R(x,2) = {\rm{0011000111000001}},\\ \ldots \\ R(x,15) = {\rm{0010011000111000}}. \end{array}$$

Let $$A \oplus B$$ denote th ...

Score: 0
Matrix formulation of Number-theoretic transforms (NTT)

I have two polynomials over a finite field. I am trying to compute the product of these polynomials using Number-theoretic transforms. For my use case, it makes sense to do this in the matrix form.

What is the matrix formulation of the NTT and inverse-NTT? Does it differ from the DFT and inverse-DFT matrices?

Score: 1
Modifying discrete logarithm problem in Zp by selecting a subset of group elements

Let $$g$$ generator of cyclic group $$Z_p$$ of order $$p-1$$, where $$g$$ can generate all group elements $$\alpha \in Z_p$$ as $$\alpha = g^x$$mod$$p$$, $$x \in (0..p-1)$$, where the discrete logarithm problem is hard, i.e. computing $$x=$$log$$_ga$$.

Suppose we instantiate a cryptographic system with the above parameters (e.g. an encryption scheme or a digital signature scheme), but with the modification of only  ...

Score: 0
RSA: why $( e^{-1} ~\text{mod}~ n \cdot \varphi(n)) ~\text{mod}~ \varphi(n) = e^{-1} ~\text{mod}~ \varphi(n)$ holds for a specific setting of RSA

Let $$p,q$$ are primes and $$n = pq$$ as in every RSA setting and now use a random $$e$$ that holds the following properties

• $$gcd(e, \phi(n)) \neq 1$$
• $$(e^{-1} ~\text{mod} ~\phi(n))^{4}\cdot3 < n$$
• $$e^{-1} ~\text{mod} ~\phi(n) < \sqrt[3]{n}$$ (integer square root), where $$\sqrt[3]{n} \in \mathbb{Z}$$

where $$\phi$$ is euler's totient function. This $$e$$ is used as the public exponent for the public ke ...

Score: 0
zkSnark Intro by Maksym Petkus: Is the polynomial defined over $Z$ or is it defined over $Z_n$?

I am reading this explanation of zkSnark written by Maksym Petkus - http://www.petkus.info/papers/WhyAndHowZkSnarkWorks.pdf

Here he has a polynomial $$p(x) = x^3 − 3x^2 + 2x$$

and the homomorphic encryption defined as $$E(c) = g^c \bmod 7$$

It's a little unclear as to where the polynomial is defined over $$Z$$ or is it defined over $$Z_7$$ - it's left a little ambiguous in the text.

This matters in the st ...

Score: 2
zkSnark: Restricting a Polynomial

I am reading this explanation of zkSnark written by Maksym Petkus - http://www.petkus.info/papers/WhyAndHowZkSnarkWorks.pdf

I have understood everything in the first 15 pages.

In 3.4 Restricting a Polynomial (Page 16)

We do already restrict a prover in the selection of encrypted powers of s, but such restriction is not enforced, e.g., one could use any possible means to find some arbitrary values

Score: 0
Setting up the discrete logarithm framework

The discrete logarithm problem over prime cyclic groups consist of finding $$x$$ satisfying $$g^x\equiv h\bmod p$$ where $$g$$ is generator of multiplicative group $$\mathbb Z/p\mathbb Z$$ at a large prime $$p$$.

There is no known algorithm to find $$g$$ in polynomial time.

1. So how does practical Discrete Logarithm systems get set up?
1. How do we know $$g$$ in fact generates the multiplicative group?

I am util ...

Score: 1
Extracting genome from a Ciphertext

Is it Probable to extract the ciphertext's genome and Visualizing it ?

Converting this:

60AD5A78FB4A4030EC542C8974CD15F55384E836554CEDD9A322D5F4135C6267
A9D20970C54E6651070B0144D43844C899320DD8FA7819F7EBC6A7715287332E
9CF31BFB66F816F319D0B7E430A5F2891553986E003720261C7E9022C0D9F11F


To this:

Encryption is like grinding the meat, once yo ...

Score: -1
Is there some function of $n$ that is a multiple of $\phi(n^2)$?

Not sure which forum to post this question so here is a link to it from MSE.

This is to adapt the approach of Fermat's Little Theorem to the Paillier encryption system.

I understand that this will occasionally fail (approximately 1 in $$\sqrt n$$), but I feel this is unlikely enough to ignore. Am I correct in my assumption?

Score: 1
Pollard's p - 1 - how do you set the bound & how do you set the base numbers

In Pollard's p-1 algorithm for factoring N, you try to find a L such that p - 1 divides L. Then you check $$gcd(pow(a,L,N)- 1, N)$$. If 1 < gcd < N, then you have found one of the factors.

I have seen 2 methods to do this.

1. For n from 1 to Bound, try $$L = n!$$ (i.e. factorial(n)) & try the $$gcd(pow(a,L,N)- 1, N)$$ for each one.
2. for n from 1 to Bound, try $$L = LCM(range(1,n))$$ & try the
Score: 0
Simple question about BGV scheme

While I'm trying to implement BGV scheme myself, I found that I'm really confusing about the encryption and decryption of the scheme. Here's my understanding:

Let $$p$$ be a plaintext modulus and $$q$$ be a ciphertext modulus (they are coprime). Let $$\mathbb{Z}_{m} = (-m/2, m/2] \cap \mathbb{Z}$$ be the fixed set of representatives modulo $$m$$ and $$[\cdot]_{m}: \mathbb{Z} \to \mathbb{Z}_{m}$$ be modulo  ...

Score: 1
Why is factorial used in Pollard's $p - 1$ algorithm?

Why exactly do we use factorial for finding an $$L$$ which is divisible by $$p - 1$$?

Pollard's algorithm is about B-powersmooth numbers & not B-smooth numbers. So where exactly does the factorial come in? Factorials aren't done by powering anything - it's just a multiplication of numbers without any exponentiation.

I am referring to Pollard's $$p - 1$$ algorithm as covered in Silverman's Mathematical C ...