Questions tagged [prime-numbers]

A prime number is an integer greater than 1 with no divisors other than itself and 1. Primes and prime products play an important role in public key cryptography.

Filter by
Sorted by
Tagged with
0
votes
1answer
546 views

Timelock puzzle improvment

I came across this question with this answer about a cryptographic timelock-puzzle that needs approximately 30 years to be solved. There is also an explanation with source code for that puzzle ...
0
votes
1answer
1k views

Solving congruences using PARI

I'm having trouble finding info in the docs about how to solve a system of congruences. The closest I can find is 'matsolvemod' in here: http://pari.math.u-bordeaux.fr/dochtml/html.stable/Vectors,...
0
votes
1answer
96 views

Prime Factorization in RSA always leads to the product of two primes?

Lets prime factorize $30$: $$30 = 3 \cdot 10 = 3 \cdot 2 \cdot 5$$ We see that the number $30$ is a product of $3$ primes. But in RSA, when factorizing huge numbers, we always seem to only get two ...
0
votes
4answers
424 views

Finding the prime factors of $n'$ given the previous $n$ and its prime factors $p$ and $q$

Say I have a very large number $n$ = $pq$ where $p$ and $q$ are prime. A new number $n'$ is generated by increasing these prime factors. How can I find this new number's prime factors?
0
votes
1answer
43 views

Breaking a modified version of Diffie Hellmann Protocol

I'm modifying the Diffie Hellman protocol as follows: We are given a large prime number $p$ and exponent $x$ such that $0 \lt x \lt p-1$ and $\mathrm{gcd}(x, p-1) = 1$. Also we pick $g$ such as $1 \lt ...
0
votes
1answer
242 views

How much (home PC) CPU time is required to generate a prime number of a given size?

How much CPU time is required on a typical home computer to generate a prime number of size 100 bit, 200 bit , 512 bit and 1024 bit using given random bits of the respective sizes? Please note that ...
0
votes
1answer
2k views

Factoring large numbers

I am trying to factor few integers that are each between 115 and 135 digits long. I was wondering if anyone knew of any efficient methods or any programs that I could use to find the two primes $p$ ...
0
votes
0answers
36 views

How do I retrieve a number which has been multiplied with a random number?

I have a 1024-bit number $n$ obtained by multiplying two 512-bit randomly generated prime numbers $p$ and $q$. Then there's $\phi = (p-1)(q-1)$, which is another 1024-bit number. I do not have $\phi$ ...
0
votes
0answers
43 views

Will a list of all prime numbers upto certain number of bits compromise crytopgraphic algorithms based on prime factorization? [duplicate]

I understand that many cryptographic algorithms depend on the difficulty of large prime factorization. Will a list of all prime numbers upto certain number of bits make it easy for an attacker to ...
0
votes
0answers
25 views

RSA encryption. Does message have to be coprime to n? [duplicate]

If I understand correctly, for RSA to work we need the message(cleartext) M $\in Z_n$ and gcd(M,n)=1. That is M coprime to n. This is to fulfil the requirement for Eulers theorem. How does RSA make ...
0
votes
1answer
56 views

ZKP for product of two primes

I'm struggling to understand the intuition of the zero knowledge-ness of this proof from the following paper. The proof is a 2 round where the verifier asks the prover to extract square roots of ...
0
votes
0answers
50 views

Trivariate Coppersmith Implementation

Bivariate Coppersmith is standard package in math software with number theory support. Bauer and Antoine Joux introduced trivariate Coppersmith in https://www.iacr.org/archive/eurocrypt2007/45150361/...
0
votes
0answers
44 views

FLT is partly applying to RSA equation, and also relation between ED mod phi and Phi + 1 mod N

After numerous attempts from myself and all of you guys, I finally came to understand RSA. I can now prove it and understand how I got there. But I still have some very few polishing questions. 1) We ...
0
votes
0answers
24 views

Three Pass Protocol Question!

Alice and Bob have agreed to use the Three Pass Protocol. p=1009 Alice chooses the encryption exponent e_A = 101 Bob chooses the encryption exponent e_B = 209 Now Alice and Bob send three ...
0
votes
0answers
41 views

About the irreducible test for a polynomial over $GF(2^m)$ (its coefficients belong to $GF(2^m)$)

For the Miller-Rabin probabilistic primality test, we can apply it to test a big number whether a probably prime number or not. Does there exist a method to test a higher-degree polynomial over $GF(2^...
0
votes
1answer
69 views

Trial division + Miller-Rabin complexity

I was reading a paper that shows time complexity of Trial division + Miller-rabin test for creating prime number. T = N(T_rnd + T_td + T_mr) T_rnd denotes time for making rnd number, T_td denotes ...
0
votes
1answer
70 views

If there is an algorithm A can calculate the modular square root of input n, How to use it to get prime factors?

Suppose you are given an algorithm $A$ which takes $y \in \{0, 1, \ldots , N − 1\}$ as input, and outputs $x \in \{0,1,\ldots,N − 1\}$ such that $x^2 \equiv y \pmod{N}$. Design an efficient, ...
0
votes
0answers
18 views

In practice, do large prime generators account for difference in gaps between primes? [duplicate]

It is my understanding that a method for creating large primes is to: pick a random large number, check the number against trial division of a set of smaller prime numbers, check with something like ...
0
votes
0answers
81 views

Yukel's Sieve - Factorization of Numbers into a Square Sieve

https://www.youtube.com/watch?v=liTTGeitpGQ https://www.youtube.com/watch?v=2nOwgiweyqc https://www.youtube.com/watch?v=rGwFsOG27DQ I came across these videos explaining a pattern that is found in ...
0
votes
0answers
68 views

Finding two primes that satisfy the conditions

I want to implement partially blind signature, and I looked at Zheng Gong's scheme. (Title: Efficient Partially Blind Signature Scheme with Provable Security) In the scheme, there is a initialization ...
0
votes
0answers
463 views

What is the danger if a non-prime is chosen for RSA? [duplicate]

I was reading this question about generating primes for RSA keys. The answers point out that most implementations of of the algorithm use probabilistic prime-ness checking algorithms. The answer by @...
0
votes
0answers
269 views

Property of Multiplicative group of integers mod n

While practising on paper I've realized of a property of multiplicative group of integers mod $n$. First, let's define $G$ being $p$ a prime and $g$ a primitive root mod n or a generator of a ...
0
votes
1answer
632 views

Euler's Totient function for semiprime numbers

I have noticed, during the period I spent studying RSA, that Euler's Totient function can be calculated in another way than $ϕ(N) =(p-1).(q-1)$ Let me explain myself by pointing to a brief example: $...
0
votes
1answer
63 views

From Factorisation of semiprimes to breaching confidentiality

If someone or some group found an efficient way to factor large composites with two distinct prime divisors, would this make it easier to decode any messages?
-1
votes
1answer
259 views

Factoring 2048 bit number is easy?

my PC found a factor for (2^2048)-1 in under a second...so does that make RSA-2048 less secure right? i used prime 95. and actually i am kinda curious how it found a factor so fast? i can even factor ...
-1
votes
1answer
264 views

Swift and (very) large integers [closed]

I am trying to write a simple Mac program to factor primes. Nothing new, but I have a problem. The largest integer I can use seems to be 2^64, which is not that big. Did you hit any similar problem? ...
-1
votes
1answer
79 views

What is the difference between these cyclic groups

$\mathbb{Z}^*_p$ vs $\mathbb{Z}^*_{p-1}$ vs $\mathbb{Z}^*_{p^2}$ vs $\mathbb{Z}^+_{p^2}$ I know $p$ is the value. The value create must be coprime to $p$. Does that mean that the value create must be ...
-1
votes
1answer
94 views

RSA encryption, Number theory [duplicate]

In RSA algorithm we have the value of $e$ & $d$ exponent and also one of the prime numbers. My question is how to produce another prime number that is not equal to the first one and the digit of a ...
-1
votes
2answers
83 views

Understanding reversible addition in a prime field

I'm trying to understand the security implications of addition in a prime field. Suppose I have X + Y = Z, occurring under prime field P(W) where W is the size of the field. If I know X and Z, I ...
-1
votes
1answer
100 views

Proving additive inverse as generator of Z*p [closed]

Let there be $p\ ,q$ odd primes, such that $p=2q+1$. Let the be $a \in Z^*_p$ so that $a \not= \pm 1(mod\ p)$. Prove that if $a$ is not a generator of $Z^*_p$ then $-a$ is a generator of $Z^*_p$.
-1
votes
1answer
74 views

Finding a prime field with n-th roots of unity

How can I find the smallest prime $p$, such that field $GF(p)$ has $n$-th roots of unity? For example, I know that for $p=2^{256} - 351 \times 2^{32} + 1$ there exit roots of unity for $n=2^{32}$. ...
-1
votes
1answer
188 views

Does Parallax Compression endanger cryptography?

http://www.novaspivack.com/science/we-have-discovered-a-new-pattern-in-the-prime-numbers-parallax-compression A lot of cryptographic algorithms depends on prime numbers. Will this influence any ...
-1
votes
1answer
4k views

why RSA uses Semiprime numbers? [duplicate]

Why does RSA use semiprime numbers? Why not just use any big number ?? What is the advantage of the two original numbers being prime? Because factoring any big number will be difficult
-1
votes
1answer
49 views

Deterministic procedure for mapping an arbitrary value into a 𝑝,𝑞 pair for public key cryptography

I want public key cryptosystem to used for re-encryption as describe in Can Paillier ,RSA or any other schemes be used for universal re-encryption like elGamal? Now i have little solution for ...
-1
votes
2answers
182 views

A quick way to justify whether $a^m \equiv 1 \pmod{n}$?

Say I would like to justify whether $10^{28} \equiv 1 \pmod{29}$. I know according to Fermat's little theorem that $a^{p-1} \equiv 1 \pmod{p}$ when $a$ is a primitive root modulo $p$. What about ...
-1
votes
1answer
150 views

Integer Factorisation

If I have a set of numbers of the form $\{ {kp+r}:k\geq0\}$ with p a prime or product of primes k large in $\in Z^+$ and r fixed, is it computationally feasible to find a factorisation for any one ...
-2
votes
1answer
162 views

Why can every prime number be written as 6k±1? [closed]

I want to know how to be sure that each prime number can be written in the form $6k±1$. How I can find the prime number that exists after a composite number with this property of prime or other ...
-2
votes
1answer
296 views

RSA and Prime numbers distribution law [duplicate]

I have read a few articles and watched some Youtube videos explaining the algorithm of RSA. It seems that RSA is mainly based on a mathematical trick (Prime Factorization). I am wondering though what'...
-2
votes
1answer
139 views

are all elements of ZpxZp in ECC definite over Zp

are all elements of ZpxZp in ECC (elliptic curve) definite over Zp ? otherwise: assume G a base point of ECC and n the order of G. why n is equal or nother to p*p ? (p a prime number). (Think to a ...
-3
votes
1answer
91 views

Are there stenography benefits to a “n-prime”?

As mentioned in this StackOverflow CodeGolf question, prime numbers can be redefined: One of my favorite definitions of the prime numbers goes as follows: 2 is the smallest prime. ...
-3
votes
2answers
211 views

Why would cryptography fall apart if there were a finite number of primes? [closed]

I vaguely know that prime numbers are very important in cryptography, but I assume for most encryption methods, they tend to stay rather 'small'. Are we really using massive prime numbers for ...

1 2 3 4 5
6