- Start with a list of all primes less than 2^(n-1).
- Form the product of all pairs of those primes.
- Delete the products that have less than n bits, or more than n bits.
How can I find all n-bit semiprime numbers?
8 views (last 30 days)
Show older comments
I know about the primes function but I need to get a list of all n-bit semiprime numbers and all the factors. Thanks.
9 Comments
Accepted Answer
John D'Errico
on 25 Jun 2022
Edited: John D'Errico
on 25 Jun 2022
Ok, I'll give in. A reasonable question, with a reason to be asked. Given a valid reason for the question, I am actuually quite happy to help. :)
The underlying problem is that of factoring large numbers. When is that difficult? When you have a number with explicitly two large prime factors. In fact, the worst such problems are probably where both factor are as close as possible to each other. Effectively, a nasty problem is one where both factors are very near sqrt(N).
The simplest scheme I would use here is based on nextprime. I wrote a version that lives in my variable precision integer codes, but there is also one in the symbolic toolbox. Unfortunately, the sym version has a limited capability in some respects. Oh well. I'll use it anyway, rather than asking you to use my own toolbox. (This will be an incentive though for me to prompt the symbolic TB team to improve their version of nextprime.)
For example, suppose I wanted to find a large semi-prime, with two factors very close to each other? I'll pick N = 50, where I want to find a semi-prime near 2^(2*N). This will be a seriously large number, and finding semi-primes near that number COULD take some effort.
m = 5; % find m semi-primes nead 2^100, all of which will suffer nasty factoring problems.
N = 50;
% First, find the first 10 primes larger than 2^N.
P_hi = zeros(m,1,'sym');
p = sym(2)^N;
for i = 1:m
p = nextprime(p+1);
P_hi(i) = p;
end
So we have now found 5 large primes, all of which exceed 2^50 by just a small amount. Next, we need to find 10 large primes, all of hich are just a weee bit less than 2^50. ARGH. I really want sym/nextprime to have been written better. So I need to do that myself? Maybe. I wanted sym/nextprime to generate the list I have above. As well, I want the ability to fine the next primes that are just LESS than the target. Hmm. I think I have a project to write soon. But even so, we can do this:
P_lo = zeros(m,1,'sym');
p = floor(sym(2)^N*0.99);
for i = 1:m
p = nextprime(p+1);
P_lo(i) = p;
end
Plist = P_lo.*P_hi;
[P_lo,P_hi,Plist]
So very efficiently generated, here are 5 distinct semi-primes, all of which are roughly 2^100. Just a bit less in fact. The two prime factors are within 1% of each other by design, so they will form arguably difficult to factor numbers. A larger such list of semi-primes would be trivially generated, just make m larger. You can make the pair of primes closer together if you wish, by making that factor of 0.99 closer to 1.
tic
factor(Plist(1))
toc
tic
factor(Plist(1) + 2)
toc
As you will expect factoring these particularly rough numbers is more difficult, taking more time than factoring some random integer in that general vicinity.
0 Comments
More Answers (0)
See Also
Categories
Find more on Number Theory in Help Center and File Exchange
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!