Mixing
Fastest way to find all the prime factors of a very large number without calculator? [closed]
-1
$begingroup$
- Largest possible factor of a very large number n would be
number itself. - The largest would be n/2 (if prime)
if n/2 is not prime then it would be less than n/2 . - The smallest factor would be 1.
Is there any general approach to find all the remaining prime factors using these three numbers?
Thanks..
prime-numbers prime-factorization prime-gaps
asked Jan 22 at 2:57
Yash PanchalYash Panchal
73
$endgroup$
closed as off-topic by RRL, Did, José Carlos Santos, Peter, Trevor Gunn Jan 28 at 16:44
This question appears to be off-topic. The users who voted to close gave these specific reasons:
- "This question is not about mathematics, within the scope defined in the help center." – Peter, Trevor Gunn
- "This question is missing context or other details: Please provide additional context, which ideally explains why the question is relevant to you and our community. Some forms of context include: background and motivation, relevant definitions, source, possible strategies, your current progress, why the question is interesting or important, etc." – RRL, Did, José Carlos Santos
If this question can be reworded to fit the rules in the help center, please edit the question.
|
show 4 more comments
-1
$begingroup$
- Largest possible factor of a very large number n would be
number itself. - The largest would be n/2 (if prime)
if n/2 is not prime then it would be less than n/2 . - The smallest factor would be 1.
Is there any general approach to find all the remaining prime factors using these three numbers?
Thanks..
prime-numbers prime-factorization prime-gaps
asked Jan 22 at 2:57
Yash PanchalYash Panchal
73
$endgroup$
closed as off-topic by RRL, Did, José Carlos Santos, Peter, Trevor Gunn Jan 28 at 16:44
This question appears to be off-topic. The users who voted to close gave these specific reasons:
- "This question is not about mathematics, within the scope defined in the help center." – Peter, Trevor Gunn
- "This question is missing context or other details: Please provide additional context, which ideally explains why the question is relevant to you and our community. Some forms of context include: background and motivation, relevant definitions, source, possible strategies, your current progress, why the question is interesting or important, etc." – RRL, Did, José Carlos Santos
If this question can be reworded to fit the rules in the help center, please edit the question.
3
$begingroup$
No, there is not.
$endgroup$
– Randall
Jan 22 at 2:57
$begingroup$
Point 1 seems incorrect. The number will not be a prime factor of itself if it is not prime (for example $2^200$ is not prime and so not a prime factor of itself, same goes for smaller numbers like 10).
$endgroup$
– Devashish Kaushik
Jan 22 at 3:05
$begingroup$
There is a fastest way to find all the prime factors of a number but I wouldn't call it fast.
$endgroup$
– Gnumbertester
Jan 22 at 3:09
2
$begingroup$
There isn't even a fast way to write down a very large number, much less find its prime factors. And for very large numbers, even calculators are useless – where will you find a calculator that keeps as many as 100 digits? Computers and exceedingly clever algorithms are the way to go.
$endgroup$
– Gerry Myerson
Jan 22 at 3:17
$begingroup$
A very large number can only be completely factored without a calculator in exceptional cases. The trial division method is far too slow, for a $200$ digit number, lets say, even the fastest computer would be overwhelmed. There are much better algorithms, which you could of course, do by hand as well in principle, but they are more complicated and still would in general need too many steps. If you do not even allow a table calculator (which I assume because of the title) , it will in general be even difficult to factor, lets say, a $9$ digit number.completely.
$endgroup$
– Peter
Jan 22 at 10:22
|
show 4 more comments
-1
-1
-1
$begingroup$
- Largest possible factor of a very large number n would be
number itself. - The largest would be n/2 (if prime)
if n/2 is not prime then it would be less than n/2 . - The smallest factor would be 1.
Is there any general approach to find all the remaining prime factors using these three numbers?
Thanks..
prime-numbers prime-factorization prime-gaps
asked Jan 22 at 2:57
Yash PanchalYash Panchal
73
$endgroup$
- Largest possible factor of a very large number n would be
number itself. - The largest would be n/2 (if prime)
if n/2 is not prime then it would be less than n/2 . - The smallest factor would be 1.
Is there any general approach to find all the remaining prime factors using these three numbers?
Thanks..
prime-numbers prime-factorization prime-gaps
prime-numbers prime-factorization prime-gaps
asked Jan 22 at 2:57
Yash PanchalYash Panchal
73
asked Jan 22 at 2:57
Yash PanchalYash Panchal
73
edited Jan 22 at 3:07
Yash Panchal
asked Jan 22 at 2:57
Yash PanchalYash Panchal
73
asked Jan 22 at 2:57
Yash PanchalYash Panchal
73
asked Jan 22 at 2:57
Yash PanchalYash Panchal
73
73
closed as off-topic by RRL, Did, José Carlos Santos, Peter, Trevor Gunn Jan 28 at 16:44
This question appears to be off-topic. The users who voted to close gave these specific reasons:
- "This question is not about mathematics, within the scope defined in the help center." – Peter, Trevor Gunn
- "This question is missing context or other details: Please provide additional context, which ideally explains why the question is relevant to you and our community. Some forms of context include: background and motivation, relevant definitions, source, possible strategies, your current progress, why the question is interesting or important, etc." – RRL, Did, José Carlos Santos
If this question can be reworded to fit the rules in the help center, please edit the question.
closed as off-topic by RRL, Did, José Carlos Santos, Peter, Trevor Gunn Jan 28 at 16:44
This question appears to be off-topic. The users who voted to close gave these specific reasons:
- "This question is not about mathematics, within the scope defined in the help center." – Peter, Trevor Gunn
- "This question is missing context or other details: Please provide additional context, which ideally explains why the question is relevant to you and our community. Some forms of context include: background and motivation, relevant definitions, source, possible strategies, your current progress, why the question is interesting or important, etc." – RRL, Did, José Carlos Santos
If this question can be reworded to fit the rules in the help center, please edit the question.
3
$begingroup$
No, there is not.
$endgroup$
– Randall
Jan 22 at 2:57
$begingroup$
Point 1 seems incorrect. The number will not be a prime factor of itself if it is not prime (for example $2^200$ is not prime and so not a prime factor of itself, same goes for smaller numbers like 10).
$endgroup$
– Devashish Kaushik
Jan 22 at 3:05
$begingroup$
There is a fastest way to find all the prime factors of a number but I wouldn't call it fast.
$endgroup$
– Gnumbertester
Jan 22 at 3:09
2
$begingroup$
There isn't even a fast way to write down a very large number, much less find its prime factors. And for very large numbers, even calculators are useless – where will you find a calculator that keeps as many as 100 digits? Computers and exceedingly clever algorithms are the way to go.
$endgroup$
– Gerry Myerson
Jan 22 at 3:17
$begingroup$
A very large number can only be completely factored without a calculator in exceptional cases. The trial division method is far too slow, for a $200$ digit number, lets say, even the fastest computer would be overwhelmed. There are much better algorithms, which you could of course, do by hand as well in principle, but they are more complicated and still would in general need too many steps. If you do not even allow a table calculator (which I assume because of the title) , it will in general be even difficult to factor, lets say, a $9$ digit number.completely.
$endgroup$
– Peter
Jan 22 at 10:22
|
show 4 more comments
3
$begingroup$
No, there is not.
$endgroup$
– Randall
Jan 22 at 2:57
$begingroup$
Point 1 seems incorrect. The number will not be a prime factor of itself if it is not prime (for example $2^200$ is not prime and so not a prime factor of itself, same goes for smaller numbers like 10).
$endgroup$
– Devashish Kaushik
Jan 22 at 3:05
$begingroup$
There is a fastest way to find all the prime factors of a number but I wouldn't call it fast.
$endgroup$
– Gnumbertester
Jan 22 at 3:09
2
$begingroup$
There isn't even a fast way to write down a very large number, much less find its prime factors. And for very large numbers, even calculators are useless – where will you find a calculator that keeps as many as 100 digits? Computers and exceedingly clever algorithms are the way to go.
$endgroup$
– Gerry Myerson
Jan 22 at 3:17
$begingroup$
A very large number can only be completely factored without a calculator in exceptional cases. The trial division method is far too slow, for a $200$ digit number, lets say, even the fastest computer would be overwhelmed. There are much better algorithms, which you could of course, do by hand as well in principle, but they are more complicated and still would in general need too many steps. If you do not even allow a table calculator (which I assume because of the title) , it will in general be even difficult to factor, lets say, a $9$ digit number.completely.
$endgroup$
– Peter
Jan 22 at 10:22
3
3
$begingroup$
No, there is not.
$endgroup$
– Randall
Jan 22 at 2:57
$begingroup$
No, there is not.
$endgroup$
– Randall
Jan 22 at 2:57
$begingroup$
Point 1 seems incorrect. The number will not be a prime factor of itself if it is not prime (for example $2^200$ is not prime and so not a prime factor of itself, same goes for smaller numbers like 10).
$endgroup$
– Devashish Kaushik
Jan 22 at 3:05
$begingroup$
Point 1 seems incorrect. The number will not be a prime factor of itself if it is not prime (for example $2^200$ is not prime and so not a prime factor of itself, same goes for smaller numbers like 10).
$endgroup$
– Devashish Kaushik
Jan 22 at 3:05
$begingroup$
There is a fastest way to find all the prime factors of a number but I wouldn't call it fast.
$endgroup$
– Gnumbertester
Jan 22 at 3:09
$begingroup$
There is a fastest way to find all the prime factors of a number but I wouldn't call it fast.
$endgroup$
– Gnumbertester
Jan 22 at 3:09
2
2
$begingroup$
There isn't even a fast way to write down a very large number, much less find its prime factors. And for very large numbers, even calculators are useless – where will you find a calculator that keeps as many as 100 digits? Computers and exceedingly clever algorithms are the way to go.
$endgroup$
– Gerry Myerson
Jan 22 at 3:17
$begingroup$
There isn't even a fast way to write down a very large number, much less find its prime factors. And for very large numbers, even calculators are useless – where will you find a calculator that keeps as many as 100 digits? Computers and exceedingly clever algorithms are the way to go.
$endgroup$
– Gerry Myerson
Jan 22 at 3:17
$begingroup$
A very large number can only be completely factored without a calculator in exceptional cases. The trial division method is far too slow, for a $200$ digit number, lets say, even the fastest computer would be overwhelmed. There are much better algorithms, which you could of course, do by hand as well in principle, but they are more complicated and still would in general need too many steps. If you do not even allow a table calculator (which I assume because of the title) , it will in general be even difficult to factor, lets say, a $9$ digit number.completely.
$endgroup$
– Peter
Jan 22 at 10:22
$begingroup$
A very large number can only be completely factored without a calculator in exceptional cases. The trial division method is far too slow, for a $200$ digit number, lets say, even the fastest computer would be overwhelmed. There are much better algorithms, which you could of course, do by hand as well in principle, but they are more complicated and still would in general need too many steps. If you do not even allow a table calculator (which I assume because of the title) , it will in general be even difficult to factor, lets say, a $9$ digit number.completely.
$endgroup$
– Peter
Jan 22 at 10:22
|
show 4 more comments
1 Answer
1
active
oldest
votes
1
$begingroup$
As you find factors you can divide them out. If there are no factors smaller than $sqrt n$ the number is prime, which is much smaller (for large $n$) than $n/2$. Factoring is believed to be hard-this is the basis of the security of RSA encryption. It is easy to prove a number composite and relatively easy to prove a number prime, but if you have a large number that is the product of two large primes it is believed to be impractical to find the factors. We don't have a proof that it is hard, but lots of people have tried and failed. If somebody did find a solution to factoring it is not clear they would publicize it because they could use it to decrypt things we believe to be secure.
answered Jan 22 at 3:15
Ross MillikanRoss Millikan
299k24200374
$endgroup$
$begingroup$
A mathematician who found a solution, and who was not working for NSA nor something like it, might publicize it in order to win a Fields Medal. On the other hand, the original idea behind modern encryption methods was developed by the NSA, and independently (and possibly earlier) by MI-V or MI-VI... A researcher who once worked for NSA said it stands for Never Say Anything.
$endgroup$
– DanielWainfleet
Jan 22 at 3:26
1
$begingroup$
@DanielWainfleet: In The Cuckoo's Egg it is claimed that there was a long era (around 1200-1300 IIRC) where the knowledge that languages had repeatable letter frequencies was only known to a handful of Europeans (though more Arabs knew it). That is the secret to breaking the substitution ciphers we see as puzzles in the newspaper. These ciphers were secure unless you hired one of those people. They wouldn't publicize it because they would lose their source of income. Easy factorization today might not be so different.
$endgroup$
– Ross Millikan
Jan 22 at 3:32
$begingroup$
To the proposer. $n$ is composite iff $n$ has a $prime$ divisor $p$ such that $ple sqrt n.$
$endgroup$
– DanielWainfleet
Jan 22 at 3:33
add a comment |
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
1
$begingroup$
As you find factors you can divide them out. If there are no factors smaller than $sqrt n$ the number is prime, which is much smaller (for large $n$) than $n/2$. Factoring is believed to be hard-this is the basis of the security of RSA encryption. It is easy to prove a number composite and relatively easy to prove a number prime, but if you have a large number that is the product of two large primes it is believed to be impractical to find the factors. We don't have a proof that it is hard, but lots of people have tried and failed. If somebody did find a solution to factoring it is not clear they would publicize it because they could use it to decrypt things we believe to be secure.
answered Jan 22 at 3:15
Ross MillikanRoss Millikan
299k24200374
$endgroup$
$begingroup$
A mathematician who found a solution, and who was not working for NSA nor something like it, might publicize it in order to win a Fields Medal. On the other hand, the original idea behind modern encryption methods was developed by the NSA, and independently (and possibly earlier) by MI-V or MI-VI... A researcher who once worked for NSA said it stands for Never Say Anything.
$endgroup$
– DanielWainfleet
Jan 22 at 3:26
1
$begingroup$
@DanielWainfleet: In The Cuckoo's Egg it is claimed that there was a long era (around 1200-1300 IIRC) where the knowledge that languages had repeatable letter frequencies was only known to a handful of Europeans (though more Arabs knew it). That is the secret to breaking the substitution ciphers we see as puzzles in the newspaper. These ciphers were secure unless you hired one of those people. They wouldn't publicize it because they would lose their source of income. Easy factorization today might not be so different.
$endgroup$
– Ross Millikan
Jan 22 at 3:32
$begingroup$
To the proposer. $n$ is composite iff $n$ has a $prime$ divisor $p$ such that $ple sqrt n.$
$endgroup$
– DanielWainfleet
Jan 22 at 3:33
add a comment |
1
$begingroup$
As you find factors you can divide them out. If there are no factors smaller than $sqrt n$ the number is prime, which is much smaller (for large $n$) than $n/2$. Factoring is believed to be hard-this is the basis of the security of RSA encryption. It is easy to prove a number composite and relatively easy to prove a number prime, but if you have a large number that is the product of two large primes it is believed to be impractical to find the factors. We don't have a proof that it is hard, but lots of people have tried and failed. If somebody did find a solution to factoring it is not clear they would publicize it because they could use it to decrypt things we believe to be secure.
answered Jan 22 at 3:15
Ross MillikanRoss Millikan
299k24200374
$endgroup$
$begingroup$
A mathematician who found a solution, and who was not working for NSA nor something like it, might publicize it in order to win a Fields Medal. On the other hand, the original idea behind modern encryption methods was developed by the NSA, and independently (and possibly earlier) by MI-V or MI-VI... A researcher who once worked for NSA said it stands for Never Say Anything.
$endgroup$
– DanielWainfleet
Jan 22 at 3:26
1
$begingroup$
@DanielWainfleet: In The Cuckoo's Egg it is claimed that there was a long era (around 1200-1300 IIRC) where the knowledge that languages had repeatable letter frequencies was only known to a handful of Europeans (though more Arabs knew it). That is the secret to breaking the substitution ciphers we see as puzzles in the newspaper. These ciphers were secure unless you hired one of those people. They wouldn't publicize it because they would lose their source of income. Easy factorization today might not be so different.
$endgroup$
– Ross Millikan
Jan 22 at 3:32
$begingroup$
To the proposer. $n$ is composite iff $n$ has a $prime$ divisor $p$ such that $ple sqrt n.$
$endgroup$
– DanielWainfleet
Jan 22 at 3:33
add a comment |
1
1
1
$begingroup$
As you find factors you can divide them out. If there are no factors smaller than $sqrt n$ the number is prime, which is much smaller (for large $n$) than $n/2$. Factoring is believed to be hard-this is the basis of the security of RSA encryption. It is easy to prove a number composite and relatively easy to prove a number prime, but if you have a large number that is the product of two large primes it is believed to be impractical to find the factors. We don't have a proof that it is hard, but lots of people have tried and failed. If somebody did find a solution to factoring it is not clear they would publicize it because they could use it to decrypt things we believe to be secure.
answered Jan 22 at 3:15
Ross MillikanRoss Millikan
299k24200374
$endgroup$
As you find factors you can divide them out. If there are no factors smaller than $sqrt n$ the number is prime, which is much smaller (for large $n$) than $n/2$. Factoring is believed to be hard-this is the basis of the security of RSA encryption. It is easy to prove a number composite and relatively easy to prove a number prime, but if you have a large number that is the product of two large primes it is believed to be impractical to find the factors. We don't have a proof that it is hard, but lots of people have tried and failed. If somebody did find a solution to factoring it is not clear they would publicize it because they could use it to decrypt things we believe to be secure.
answered Jan 22 at 3:15
Ross MillikanRoss Millikan
299k24200374
answered Jan 22 at 3:15
Ross MillikanRoss Millikan
299k24200374
answered Jan 22 at 3:15
Ross MillikanRoss Millikan
299k24200374
answered Jan 22 at 3:15
Ross MillikanRoss Millikan
299k24200374
299k24200374
$begingroup$
A mathematician who found a solution, and who was not working for NSA nor something like it, might publicize it in order to win a Fields Medal. On the other hand, the original idea behind modern encryption methods was developed by the NSA, and independently (and possibly earlier) by MI-V or MI-VI... A researcher who once worked for NSA said it stands for Never Say Anything.
$endgroup$
– DanielWainfleet
Jan 22 at 3:26
1
$begingroup$
@DanielWainfleet: In The Cuckoo's Egg it is claimed that there was a long era (around 1200-1300 IIRC) where the knowledge that languages had repeatable letter frequencies was only known to a handful of Europeans (though more Arabs knew it). That is the secret to breaking the substitution ciphers we see as puzzles in the newspaper. These ciphers were secure unless you hired one of those people. They wouldn't publicize it because they would lose their source of income. Easy factorization today might not be so different.
$endgroup$
– Ross Millikan
Jan 22 at 3:32
$begingroup$
To the proposer. $n$ is composite iff $n$ has a $prime$ divisor $p$ such that $ple sqrt n.$
$endgroup$
– DanielWainfleet
Jan 22 at 3:33
add a comment |
$begingroup$
A mathematician who found a solution, and who was not working for NSA nor something like it, might publicize it in order to win a Fields Medal. On the other hand, the original idea behind modern encryption methods was developed by the NSA, and independently (and possibly earlier) by MI-V or MI-VI... A researcher who once worked for NSA said it stands for Never Say Anything.
$endgroup$
– DanielWainfleet
Jan 22 at 3:26
1
$begingroup$
@DanielWainfleet: In The Cuckoo's Egg it is claimed that there was a long era (around 1200-1300 IIRC) where the knowledge that languages had repeatable letter frequencies was only known to a handful of Europeans (though more Arabs knew it). That is the secret to breaking the substitution ciphers we see as puzzles in the newspaper. These ciphers were secure unless you hired one of those people. They wouldn't publicize it because they would lose their source of income. Easy factorization today might not be so different.
$endgroup$
– Ross Millikan
Jan 22 at 3:32
$begingroup$
To the proposer. $n$ is composite iff $n$ has a $prime$ divisor $p$ such that $ple sqrt n.$
$endgroup$
– DanielWainfleet
Jan 22 at 3:33
$begingroup$
A mathematician who found a solution, and who was not working for NSA nor something like it, might publicize it in order to win a Fields Medal. On the other hand, the original idea behind modern encryption methods was developed by the NSA, and independently (and possibly earlier) by MI-V or MI-VI... A researcher who once worked for NSA said it stands for Never Say Anything.
$endgroup$
– DanielWainfleet
Jan 22 at 3:26
$begingroup$
A mathematician who found a solution, and who was not working for NSA nor something like it, might publicize it in order to win a Fields Medal. On the other hand, the original idea behind modern encryption methods was developed by the NSA, and independently (and possibly earlier) by MI-V or MI-VI... A researcher who once worked for NSA said it stands for Never Say Anything.
$endgroup$
– DanielWainfleet
Jan 22 at 3:26
1
1
$begingroup$
@DanielWainfleet: In The Cuckoo's Egg it is claimed that there was a long era (around 1200-1300 IIRC) where the knowledge that languages had repeatable letter frequencies was only known to a handful of Europeans (though more Arabs knew it). That is the secret to breaking the substitution ciphers we see as puzzles in the newspaper. These ciphers were secure unless you hired one of those people. They wouldn't publicize it because they would lose their source of income. Easy factorization today might not be so different.
$endgroup$
– Ross Millikan
Jan 22 at 3:32
$begingroup$
@DanielWainfleet: In The Cuckoo's Egg it is claimed that there was a long era (around 1200-1300 IIRC) where the knowledge that languages had repeatable letter frequencies was only known to a handful of Europeans (though more Arabs knew it). That is the secret to breaking the substitution ciphers we see as puzzles in the newspaper. These ciphers were secure unless you hired one of those people. They wouldn't publicize it because they would lose their source of income. Easy factorization today might not be so different.
$endgroup$
– Ross Millikan
Jan 22 at 3:32
$begingroup$
To the proposer. $n$ is composite iff $n$ has a $prime$ divisor $p$ such that $ple sqrt n.$
$endgroup$
– DanielWainfleet
Jan 22 at 3:33
$begingroup$
To the proposer. $n$ is composite iff $n$ has a $prime$ divisor $p$ such that $ple sqrt n.$
$endgroup$
– DanielWainfleet
Jan 22 at 3:33
add a comment |
3
$begingroup$
No, there is not.
$endgroup$
– Randall
Jan 22 at 2:57
$begingroup$
Point 1 seems incorrect. The number will not be a prime factor of itself if it is not prime (for example $2^200$ is not prime and so not a prime factor of itself, same goes for smaller numbers like 10).
$endgroup$
– Devashish Kaushik
Jan 22 at 3:05
$begingroup$
There is a fastest way to find all the prime factors of a number but I wouldn't call it fast.
$endgroup$
– Gnumbertester
Jan 22 at 3:09
2
$begingroup$
There isn't even a fast way to write down a very large number, much less find its prime factors. And for very large numbers, even calculators are useless – where will you find a calculator that keeps as many as 100 digits? Computers and exceedingly clever algorithms are the way to go.
$endgroup$
– Gerry Myerson
Jan 22 at 3:17
$begingroup$
A very large number can only be completely factored without a calculator in exceptional cases. The trial division method is far too slow, for a $200$ digit number, lets say, even the fastest computer would be overwhelmed. There are much better algorithms, which you could of course, do by hand as well in principle, but they are more complicated and still would in general need too many steps. If you do not even allow a table calculator (which I assume because of the title) , it will in general be even difficult to factor, lets say, a $9$ digit number.completely.
$endgroup$
– Peter
Jan 22 at 10:22