All Questions
Tagged with prime-factorization cryptography
31
questions
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