How can I find all n-bit semiprime numbers?

I know about the primes function but I need to get a list of all n-bit semiprime numbers and all the factors. Thanks.

[John D'Errico]

Yet another question that seems highly likely to be homework, but at the same time, perhaps not. At the same time, you need to remember the list will be a long one if the number of bits is large. However, then I look at your other questions, and it seems you have asked some fairly simple questions, one of which is quite close. That makes it far more likely this is homework.

1. Start with a list of all primes less than 2^(n-1).
2. Form the product of all pairs of those primes.
3. Delete the products that have less than n bits, or more than n bits.

Surely you can handle step 1.

As for step 2, just read the responses to one of the last questions you asked.

Finally, how can you compute the number of bits in a number? What would log2 tell you?

If you want a less memory intensive solution, surely you can do exactly the same thing using a loop, computing products of pairs of primes, saving those that have exactly n bits. Again, log2 would be your friend here, since it will allow you to efficiently know which primes to use in that product. A careful implementation would even allow you to do this efficiently, by computing the log2 of every prime in the initial list.

Finally, If you convinced me this is not homework by explaining why you want this list, AND you showed a reasonably serious effort you made, I would offer more help. I'll bet it is homework though.

[Torsten]

@John D'Errico

Wouldn't you agree that every question asked here is some kind of "homework" ?

[John D'Errico]

@Torsten, well, often many such questions are. But when a basic question about mathematics like this is asked, with no attempt at solving it, then it fails my smell test. A student needs to make an effort, else they learn nothing. Homework was assigned to the student, not for the student to then go find someone who can answer their question. It is not a problem if a student is unable to answer every homework problem they are given. That just may mean they need to spend more time doing their homework, or it may mean they are in the wrong class. Homework is given to a student to teach them something, here hopefully about both mathematics and about MATLAB.

By the way, for those who don't know what the original question drives at, a semi-prime is an integer that is formed as exactly a product of two primes.

https://en.wikipedia.org/wiki/Semiprime

So a number with only two factors, both of which are prime. The factors need not be distinct. 289 is a semi-prime, since it is 17*17. As well, 143 is a semi-prime, as it is 11*13. But 144 is not a semi-prime, since while it has factors of only 2 and 3, they each appear more than once in the list of all prime factors.

The list of n-bit semi-primes would be long for moderately large n. So for n=50, for example, we would have the number 2*p, where p here is the smallest prime just less than 2^49. Using my nextprime utility, that would seem to be:

p = nextprime(2^49,'below')
p =
562949953421231

and therefore 2*p will be a 50 bit semi-prime.

2*sym(p)
ans =
1125899906842462

dec2bin(2*sym(p))
ans =
'11111111111111111111111111111111111111111101011110'

numel(ans)
ans =
50

However, you would seriously not wish to generate the list of all 50 bit semi-primes, as that list would be immense. Remember, there are a gajillion primes less than 2^49 (ok, not quite, but a long list, with approximately this many of them:

2^49/log(2^49)
ans =
16574798083053.1

So roughly 16 trillion such primes. And that means the list of 50 bit semi-primes would be HUGE.

An interesting question is to find twin semi-primes, so number pairs that are both semi-prime, and are adhacent on the number line. We can find such pairs easily enough, thus [9,10], and [38,39]. Regardless, as much as the question is technically interesting, if it is homework, it needs some effort made by the student.

Anyway, IF @Nadatimuj were able to explain why, rationally, they needed such a list of n-bit semi-primes, in a context that was not to just do their current homework assignment, I would be quite happy to offer lots of help. As well, if they made some serious effort, even if it was homework, then I'd be happy to offer at least some help. The problem is, if I just do their homework here, they learn nothing, except there is a sucker born every minute.

[Nadatimuj]

@John D'Errico Thanks for your reply, and just to clarify I am doing reseach, not homeworks. I have an Ising machine that is supposed to solve combinatorial optimization problems...and in this case, we decided to factor semiprime numbers. I can definitely code it myself but the reason I post in this forum is I often find codes here are more optimized and fast. I need to run 1000s of trials, so for any code even a 0.001s time saving helps a lot.

The code I have is slow for large numbers, and actually I don't need all the numbers, I only need 10 unique semiprime numbers for each size up to 32 bits. Thanks!

clc
clearvars

factor_size = 10

prime_factors = primes(2^factor_size);  % getting primes
prime_factors = prime_factors(log2(prime_factors)>factor_size-1);
prime_factors(randperm(length(prime_factors)));
semiprimes = unique(prime_factors.*prime_factors.')

[John D'Errico]

Ok, I'll accept that you do have a viable problem. Sorry for being difficult, but you can imagine there are many students who just toss their homework on the site and then expect a response. with no effort made on their part. I'll post an answer to your question, specifically targeted at difficult to solve factoring problems.

[Torsten]

@Nadatimuj

Thanks for your reply, and just to clarify I am doing reseach, not homeworks.

Research, homeworks - what's the difference ? A winged word in Germany is a wording from our former chancellor, Helmut Kohl, who claimed that "every nation in the EU should try to get its homeworks done properly in order to be convincing towards its partners". So "homework" is open to interpretation.

[John D'Errico]

I think this is an important distinction. Research, by itself is not sufficient to get my respect. If someone were to ask, "Will you please help me to write the code for my thesis on some obscure topic?". That sort of question deserves no help, since it is just asking for help to solve a problem the poster has been tasked to do. On the other hand, if someone shows some progress, yet has a stumbling block in their attempts to move forwards, as long as they show a reasonable attempt made, they gain my respect. Asking for help is not in itself bad. The problem is in giving up, with no effort shown or made.

[Torsten]

The problem is in giving up, with no effort shown or made.

Yes, that's the decisive distinction. But here, the usual terminology is "This smells like homework" where it should read "This smells like laziness".

[Nadatimuj]

@John D'Errico Thanks for the code, it is perfect!

When I mean research I mean is: I am responsible to develop the Ising machine I am trying to build that will factorize many numbers. Generating semiprime number is nothing novel or not treated as a research topic in my case. Yes, in many cases problem generation is also an important reseach topic, but if it is not something new, it's not even something publishable. Thank you both.

Answer 1

[John D'Errico]

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]

ans = 

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))

ans = 

toc

Elapsed time is 0.513973 seconds.

tic
factor(Plist(1) + 2)

ans = 

toc

Elapsed time is 0.070427 seconds.

As you will expect factoring these particularly rough numbers is more difficult, taking more time than factoring some random integer in that general vicinity.