All Questions
Tagged with prime-factorization cryptography
31
questions
1
vote
1
answer
99
views
distribution of square roots of unity $mod n$ | Factoring with inverse pair
I am writing a proof related to the RSA cryptosystem, specifically showing that given an inverse pair $d, c$ under multiplication mod $\phi(N)$, where
$$ dc \equiv 1 \pmod{\phi(N)}, $$
there exists a ...
- 83
2
votes
0
answers
50
views
The number of integers less than x that have at least two distinct prime factors of bit size greater than one-third the bit size of x
Sander came out with a paper describing how to generate what he calls an RSA-UFO. Anoncoin then utilizes this and mentions that the paper proves that the probability that a randomly generated integer, ...
- 123
2
votes
1
answer
67
views
Is factoring primes $pq$ eqivalent to discovering $p+q$, thus binding $q$ and the search for $(p+q)$ when $(q/p) < 4$?
Background
Some crypto algorithms rely principally on the difficulty of factoring two prime numbers $p$ and $q$. For the purpose of this discussion, assume $p<q$.
(The top of this article is ...
- 277
1
vote
0
answers
204
views
Understanding the ramifications of Riemann Hypothesis
Proving Riemann Hypothesis is a million dollar problem, but I am more interested in understanding its ramifications in the practical world.
According to many sources, one such effect will be ...
- 395
2
votes
0
answers
142
views
Factor base for RSA cryptosystem
In RSA crptosystem, we choose two big primes $p,q$ and set $n=pq$. $n$ is public and roughly, the aim is factorize $n$ to decrypt the encrpyted message.
A method to attack the system is the following:...
- 2,807
6
votes
2
answers
188
views
Can irreversibility of trapdoor functions generally not be proved?
The German Wikipedia article on asymmetric cryptography states that asymmetric cryptography is always based on assumptions which can not be proven:
Die Sicherheit aller asymmetrischen Kryptosysteme ...
- 163
0
votes
1
answer
106
views
Given that $n = 1279033001$ is a product $n = pq$ of distinct primes $p$ and $q$ and that $175205^2 ≡ 1$(mod n), factorise $n$.
I have tried using Fermats factorisation and Pollard $p-$method but unfortunately I'm running into rounding errors with my calculator. I'm not sure how $175205^2 ≡ 1$(mod n) is helpful
- 11
3
votes
1
answer
236
views
Factorization of large (60-digit) number
For my cryptography course, in context of RSA encryption, I was given a number $$N=189620700613125325959116839007395234454467716598457179234021$$
To calculate a private exponent in the encryption ...
- 1,218
5
votes
1
answer
190
views
What other uses are there for Prime numbers? [duplicate]
Simple question out of curiosity...
Beside the use of cryptographic safety and prime factorization, what other uses are there for prime numbers?
Thank you.
Edit:
To clarify and not confusing with ...
- 61
1
vote
1
answer
272
views
"Theorems on factorization and primality testing" Reference request
I would like to ask two questions :
Is John M. Pollard's 1974 paper Theorems of factorization and primality testing available online for free ?
Independently of that : where can I find the material ...
- 20.4k
2
votes
0
answers
272
views
In the General Number Field Sieve, can we estimate the size of the matrix in terms of the number being factored?
One of the last steps of GNFS is to solve a large matrix-vector equation (usually using the Block Lanczos algorithm or the Block Wiedemann algorithm). The matrix for the most recent RSA number ...
- 1,068
3
votes
1
answer
113
views
What does it mean for $\sigma^N$≡$\sigma^e$ (mod N) for arbitrary a?
Full disclosure: I am trying to solve a homework problem.
As part of a homework problem, we were given a large semiprime $N$, which was used as both the modulus and the public key and asked to ...
- 259
1
vote
1
answer
449
views
Manual factorization of a large number in hexadecimal format
I have a large hexadecimal number that I'd like to factorize in two prime numbers. I am sure that this number can be built with two primes. It can't be done with the computer because it's a very large ...
- 13
1
vote
1
answer
162
views
RSA number factors (is semiprime)
I have the $n$ RSA number of a message, i need to find the $p,q$ prime factors of $n$ to find the private key.
I have $n$, and $e$. This is for a challenge and i think this number was previously ...
- 94
2
votes
0
answers
503
views
Using factorization to solve modulo arithmetic involving big numbers.
In one of my classes, the following approach was shown to solve modulo operations involving huge numbers:
Problem to solve:
49 10 mod 187.
Approach taken:
Prime factorize $187$. It's factors are ...
- 141