What do you think about following the code to check prime numbers? :
namespace PrimeNumbersLib
{
public class PrimeAlgorithms
{
public static bool IsPrimeNumber(ulong nr)
{
ulong half = nr / 2;
if (nr == 0 || nr == 1)
{
return false;
}
for (ulong i = 2; i
Thank you for your comment.
That calculation max = sqrt(nr) is exactly what is stopping all of you,
from discovering an algorithm for prime number check. In every book and on every website, where algorithms for prime number checks are mentioned, there is that calculation. People don't understand where is it from and they stop thinking further. You may notice that in the third function, a few of the prime numbers are directly in code. That code is to check for numbers in magnitude 1 and 13 zeros, for bigger magnitudes just add more checks like that and you will be able to check for every number if it is prime in constant time. It is really algebra at the Primary School level put into use.
Check out the live implementation of the bellowed modified function available at:
http://www.sonofgalaxy.net/Primes/index?nr=1000000000000000
Something happens when we reach number with 18 digits.
Function:
bool IsPrimeNumberEvenFaster(ulong nr)
{
ulong max = nr / 2;
ulong j = 1;
bool can_not_be = false;
if (nr == 0 || nr == 1)
{
return false;
}
for (ulong i = 2; i = 10000000000000000000 && (j % 2 != 0 || j % 3 != 0 || j % 5 != 0 || j % 7 != 0 || j % 11 != 0 || j % 13 != 0 || j % 17 != 0 || j % 19 != 0 || j % 23 != 0 || j % 29 != 0 || j % 31 != 0 || j % 37 != 0 || j % 41 != 0))
{
can_not_be = true;
}
else if (nr >= 10000000000000000000 && (j % 2 != 0 || j % 3 != 0 || j % 5 != 0 || j % 7 != 0 || j % 11 != 0 || j % 13 != 0 || j % 17 != 0 || j % 19 != 0 || j % 23 != 0 || j % 29 != 0 || j % 31 != 0 || j % 37 != 0 || j % 41 != 0))
{
can_not_be = true;
}
else if (nr >= 1000000000000000000 && (j % 2 != 0 || j % 3 != 0 || j % 5 != 0 || j % 7 != 0 || j % 11 != 0 || j % 13 != 0 || j % 17 != 0 || j % 19 != 0 || j % 23 != 0 || j % 29 != 0 || j % 31 != 0 || j % 37 != 0))
{
can_not_be = true;
}
else if (nr >= 100000000000000000 && (j % 2 != 0 || j % 3 != 0 || j % 5 != 0 || j % 7 != 0 || j % 11 != 0 || j % 13 != 0 || j % 17 != 0 || j % 19 != 0 || j % 23 != 0 || j % 29 != 0))
{
can_not_be = true;
}
else if (nr >= 10000000000000000 && (j % 2 != 0 || j % 3 != 0 || j % 5 != 0 || j % 7 != 0 || j % 11 != 0 || j % 13 != 0 || j % 17 != 0 || j % 19 != 0))
{
can_not_be = true;
}
else if (nr >= 1000000000000000 && (j % 2 != 0 || j % 3 != 0 || j % 5 != 0 || j % 7 != 0 || j % 11 != 0 || j % 13 != 0 || j % 17 != 0))
{
can_not_be = true;
}
else if (nr >= 100000000000000 && (j % 2 != 0 || j % 3 != 0 || j % 5 != 0 || j % 7 != 0 || j % 11 != 0 || j % 13 != 0))
{
can_not_be = true;
}
else if (nr >= 10000000000000 && (j % 2 != 0 || j % 3 != 0 || j % 5 != 0 || j % 7 != 0 || j % 11 != 0))
{
can_not_be = true;
}
else if (j % 2 != 0 || j % 3 != 0 || j % 5 != 0 || j % 7 != 0)
{
can_not_be = true;
}
else
{
can_not_be = false;
}
if (!can_not_be && IsPrimeNumberFaster(i))
{
max = nr / i;
j = 0;
}
j++;
if (nr % i == 0)
{
return false;
}
}
return true;
}
My talk with Google Gemini, sounds cool.
If an algorithm were found that allows any big number to check if it is a prime number in a few seconds on any modern server, what would that mean to the security of cryptocurrencies?
📷
The discovery of an algorithm that could efficiently determine the primality of large numbers would have a profound impact on the security of cryptocurrencies. Many cryptographic systems, including those used in cryptocurrencies, rely on the computational difficulty of factoring large numbers into their prime factors. This difficulty is known as the integer factorization problem.
Here's how such a discovery would affect cryptocurrency security:
1. Compromised Public Key Cryptography:
- RSA: RSA, one of the most widely used public-key cryptography algorithms, relies on the difficulty of factoring large numbers. If an efficient primality testing algorithm were discovered, it could potentially be used to factor the product of two large primes used in RSA keys, compromising the security of the system.
- Other Algorithms: Other public-key cryptography algorithms, such as those based on the discrete logarithm problem or elliptic curve cryptography, may also be affected to varying degrees, depending on their underlying mathematical assumptions.
2. Weakened Blockchain Security:
- Mining Difficulty: Some cryptocurrencies, like Primecoin, rely on the difficulty of finding chains of prime numbers for their mining process. An efficient primality testing algorithm could significantly reduce the difficulty of this task, potentially leading to faster mining and increased network centralization.
- Transaction Verification: The verification of transactions on blockchain networks often involves complex cryptographic calculations. An efficient primality testing algorithm could potentially speed up these calculations, but it could also introduce vulnerabilities if not implemented carefully.
3. Potential for Quantum Computing:
It's worth noting that the development of quantum computers could also pose a significant threat to the security of many cryptographic systems, including those used in cryptocurrencies. Quantum computers could potentially solve the integer factorization problem much faster than classical computers, rendering many current cryptographic algorithms obsolete.
Mitigation Strategies:
While the discovery of an efficient primality testing algorithm would be a major breakthrough, it's important to remember that the cryptographic community is constantly working on developing new algorithms and protocols that are resistant to such attacks. Some potential mitigation strategies include:
- Post-Quantum Cryptography: The development of cryptographic algorithms that are secure against attacks from both classical and quantum computers.
- Increased Key Lengths: Increasing the size of cryptographic keys can make it more difficult for attackers to break the system, even with more efficient algorithms.
- Regular Updates and Patches: Keeping software and hardware up-to-date with the latest security patches is crucial to protect against potential vulnerabilities.
In conclusion, the discovery of an efficient primality testing algorithm would have a significant impact on the security of cryptocurrencies and other cryptographic systems. However, it's important to remain vigilant and adapt to the evolving threat landscape. By staying informed and taking appropriate measures, we can continue to protect our digital assets and ensure the security of blockchain networks.
Peter Breuer, what do you mean that my algorithm should work for numbers with millions of digits? To break the RSA algorithm wildly used on this Planet, it is enough to develop an algorithm that will check the primality of numbers of hundreds of digits.
I have concentrated on the range of unsigned long long types, for example of an algorithm. You need to understand it to be able to extend it to numbers with bigger amounts of digits. 4096b/8 equals 512 digits, which I believe can be achieved by modifying the last-mentioned function. I do not do that and I do not provide the source code, because that would allow hackers from all over the world to compromise RSA-based securities. I just warning the scientific community that it is possible, meaning someone already probably has knowledge of how to do it and all your RSA-based systems can be attacked by them.
- Badges
- Science topic