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
Laba Sa avatar
Sage code for finding generator matrix of MDS code
in flag
  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?
de flag

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
untitled avatar
Matrix formulation of Number-theoretic transforms (NTT)
cn flag

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
do flag

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
Cryptomathician avatar
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
in flag

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$?
et flag

I am reading this explanation of zkSnark written by Maksym Petkus -

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
et flag

I am reading this explanation of zkSnark written by Maksym Petkus -

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
Turbo avatar
Setting up the discrete logarithm framework
ru flag

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
R1w avatar
Extracting genome from a Ciphertext
tn flag

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

Converting this:


To this:

ciphers genome

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

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

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
et flag

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
Seewoo Lee avatar
Simple question about BGV scheme
pk flag

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?
et flag

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