All Questions
Tagged with prime-factorization cryptography
31
questions
1
vote
1
answer
101
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
144
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
273
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
273
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
450
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 ...
- 84
2
votes
0
answers
505
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
5
votes
3
answers
1k
views
How to factorise large number without calculator? [duplicate]
I would like to factorise $496241$. I know the answer is $677 \times 733$. But I don't know how to get there.
Here is the full question:
"A message has been encoded using RSA with a modulus of $m =...
- 59
1
vote
1
answer
2k
views
Create a private key from two public keys that share primes
Given two public keys, n1 and n2 (and e the exponent)--how would one generate a private key ...
2
votes
1
answer
223
views
Prime Factorization: a different approach
I was wondering if any of you experts out there would consider the following to be of any merit.
Given a composite integer, the product of two unique primes (p=nq), an isosceles trapezoid can be ...
- 37
2
votes
2
answers
71
views
Factors of integers of the form $p-2^\lambda n$.
Here $p$ is an odd prime, $n$ is uniform on $[0, 2^\lambda]$, and $\lambda$ is a constant. We define distribution $\mathcal{D}$ by:
$$x \xleftarrow{\$} p-2^\lambda n$$
Assume $p \approx 2^{4\lambda}$,...
- 121
1
vote
0
answers
347
views
Is it difficult to factor a product of many large primes?
It's well known that it is difficult to factor a product of two large primes, and this fact is used in cryptography.
Is it also difficult to factor a product of $n$ large primes?
- 57
0
votes
1
answer
133
views
Number Theory Problem Involving RSA
The House of Lilliput is using RSA encryption to receive secret messages from all the realms. They have published their public encoding exponent $e = 37$ and their public modulus $M = pq = 527$.
Find ...
- 1,221
0
votes
1
answer
722
views
Solve $a^2 \equiv b^2\ (mod\ N)$ by factoring number N?
Find values $a$ and $b$ which satisfies $a^2 \equiv b^2\ (mod\ N)$ by factoring number $N = 52907$. Use given identities:
$$399^2 \equiv 480\ (mod\ N)\ \ \ 480 = 2^5 * 3 * 5$$
$$763^2 \equiv 192\ (...
- 199
2
votes
0
answers
2k
views
Discrete Logarithm vs Integer Factorization
Can anyone please tell me if finding discrete logarithm is considered more difficult than integer factorization?
We have very advanced methods to find factors of large composite numbers like Number ...
- 305
2
votes
0
answers
95
views
How Do Computers Factor Semi-Primes [closed]
How do computers factor large semi-primes? I know it's difficult but what process do they use? Is it simply a matter of dividing by all odd numbers under the square root of the semi-prime till they ...
- 21
1
vote
2
answers
362
views
Finding the upper bound for a number's factors length
Okay, so the title is a bit misleading but I had to keep it short.. Anyhow, if I have a number X what will the length of it's longest two factors be?
For example:
$X = 10000$
I want $3$ and $3$ (...
- 353
3
votes
1
answer
156
views
Does this approach for factorizing RSA numbers help in any way?
I was thinking about why factorizing RSA numbers is so hard. When humans perform any kind of maths manually, they often employ various 'tricks' that get them closer to the answer. Some are based on ...
- 2,032
2
votes
1
answer
2k
views
attack on RSA (factoring when knowing e and d)
This is the problem, I have to explain how works the algorithm on the image with modular arithmetic for a discrete math class., I tried to explain it, but I couldn´t. In the class, I have seen this ...
- 23
6
votes
1
answer
2k
views
Lenstra's Elliptic Curve Algorithm
I am currently trying to understand Lenstra's Elliptic Curve Algorithm for factoring integers.
As a source I use "Rational Points on Elliptic Curves" by Joseph H. Silverman and John Tate.
They ...
- 1,646
3
votes
3
answers
567
views
can it be proven that something is "difficult" (prime factoring for example)
I understand that the current state of the art suggests that factoring into primes is a difficult problem. I also understand that a large part of public key cryptography seems to be based on that ...
- 133
0
votes
2
answers
242
views
Relating calculus to RSA and/or prime factorization?
I'm writing a math paper on RSA and it would be nice if it had some calculus in it. Is RSA directly related to calculus in any manner? This can include proving theorems, generating keys, or cracking ...
- 459
4
votes
1
answer
607
views
Probability of an ECM factor
Suppose I have a composite number $N$ divisible by some prime $p\le x.$ What is the probability that one iteration of ECM finds $p$, given parameters B1 and B2?
Usually people look for factors in ...
- 32.3k