Questions tagged as ['number-theory']

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

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

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?

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

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

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

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

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?

2. How do we know $g$ in fact generates the multiplicative group?

I am util ...

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

Converting this:

60AD5A78FB4A4030EC542C8974CD15F55384E836554CEDD9A322D5F4135C6267
A9D20970C54E6651070B0144D43844C899320DD8FA7819F7EBC6A7715287332E
C8675C136183B3F8A1F81EF969418267130A756FDBB2C71D9A667446E34E0EAD
9CF31BFB66F816F319D0B7E430A5F2891553986E003720261C7E9022C0D9F11F

To this:

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

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?

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

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

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