PARI's commands

[CRGreathouse]

Originally Posted by 3.14159

Initially, I meant "general semiprimes", due to the comparisons between how many bases a 2nd kind Cunningham semiprime is pseudoprime to, compared to a general semiprime.

Unfortunately I tossed my earlier code. But I can rewrite it readily enough. And better this time!

Let's see... how to go about generating a random semiprime. Suppose we want one in the range (a, b] with b - a large compared to log^2 b and b/a small. There are semiprimes divisible by 3, etc. So to choose the size of the smaller prime factor we give each prime weight equal to its reciprocal and select from the total size at random.

So if the range is (2^99, 2^100] then we want to give 2 weight 1/2, 3 weight 1/3, ..., and 1125899906842597 weight 1/1125899906842597. (I'm going to ignore issues about choosing toward the end of the range here.) The total weight is going to be about M + log log sqrt b.* So generate a random number uniformly at random up to that total, subtract M, and exponentiate twice, choosing a prime around there. Then generate the other factor as appropriate.


* Dusart's recent preprint gives reasonably tight bounds on this. Pity, though, I don't know of a correcting term, because there certainly seems to be one.

[3.14159]

Alternatively, you could just multiply two random primes together. No need for much math work on generating a set of random primes to multiply together to form a semiprime.

Wait.. disregard the above.

[CRGreathouse]

Originally Posted by 3.14159

Well, a promising clue is right here.

I'm familiar with that paper. Also of interest is "On the distribution of pseudoprimes" which he published the following year, giving an upper bound,

But I thought you were looking at strong pseudoprimes, not Fermat pseudoprimes. In that case "Average case error estimates for the strong probable prime test" is probably more appropriate, though I don't remember if they define an analogue for P(x).

[CRGreathouse]

Originally Posted by science_man_88

I was thinking of making pari write the program itself before taking over the world lol (just joking about the taking over the world).

I'm not sure which one would be harder.

Originally Posted by science_man_88

a program making a program seems like a virus but this idea sounds cool.

Agreed. I've written program that generate other programs -- even as a child, I wrote a bitmap graphics program that would output a BASIC program drawing what you wanted (so that I could include it in my own program, naturally).

Originally Posted by science_man_88

one thing I've thought of is using a text to speech translator like what Microsoft has in Windows(though if possible better) and instead of turning it to speech interpret its meaning and spit out a program based on what it can understand(hopefully a lot).

That sounds harder yet.

I suggest breaking the task down into simple parts and working on them separately. That way you won't get discouraged by the difficulty of the whole task -- and you can have something that you can finish in an hour rather than in a lifetime.

[science_man_88]

lets say it was on the same computer all together we have:

1) read the problem to the script
2) decipher the meaning of the problem
3) output a code that does what the problem needs.


the main one when it's on one computer is 2) decipher the meaning of the problem.

example if the problem is read as:

find all primes from x upto/until/to n

the key words/phrasings I see are 1)find - suggest to most I think that they may not necessarily want to have them printed to them but to get them for further use (though printing is a further use in one sense)

2)all primes-means they don't want any missed.

3)from-shows us there's a range involved and that that range may be anywhere on the number line (so we can just assume 1 in this case).

4)x-our lower limit if it's odd if not it's x+1 (except when x = 2) that is our lower limit.

5) upto/until/to- these all mean in the positive direction last i checked.

6) n-our upper bound.

so generically they want:

forprime(p=x,n,do something else/likely print())

or if any number in range x...n is out of primelimit bounds

for(p=x,n,if(isprime(p),do something else/likely print()))

in this case we used every word but in more vague cases or less specific cases it might not be so.

[CRGreathouse]

Agreed, 2 does seem the hardest. 1 is easy.

So why don't you focus on #3. It's not completely trivial, but unlike #2 it isn't a lifetime research project.

[science_man_88]

Originally Posted by CRGreathouse

Agreed, 2 does seem the hardest. 1 is easy.

So why don't you focus on #3. It's not completely trivial, but unlike #2 it isn't a lifetime research project.

doesn't 3 depend on 2 ?

I used the words to decipher the meaning and in doing so I was able to give possible codes.

[CRGreathouse]

OK, here's my program for generating random semiprimes. It's not perfect, but it gives reasonable results I think. And the speed should be fast even when working with large numbers.

If you need higher-quality results, you'd want correction factors for M when generating p and a different method entirely for selecting q. The first takes mathematical knowledge and programmer time to implement, but wouldn't make the program run much more slowly at all; the second takes little time to implement (< 10 minutes) but would cause the program to run perhaps ~100 times more slowly at large numbers.

rsp(b,flag=0)={
	if(b<7,
		if(b<3, error("No semiprimes with fewer than 3 bits"));
		if(type(b) != "t_INT", error("Bad type in rsp"));
		my(n);
		if(b==3,n=[4,6]);
		if(b==4,n=[9,10,14,15]);
		if(b==5,n=[21,22,25,26]);
		if(b==6,n=[33,34,35,38,39,46,49,51,55,57,58,62]);
		n=n[random(#n)+1];
		return(if(flag,factor(n),n))
	);

	\\ Choose the small prime as 2 with probability 1/2, 3 with probability 1/3, etc.
	my(M=.261497212847642783755,weight=log(b*log(2)/2)+M,r=random(round(weight << 64))*1.>>64,p=precprime(exp(exp(r-M))),q);
	q=2^b\p;
	q=nextprime(q\2+random(q\2));
	if(p > q,
		b = p;
		p = q;
		q = b;
	);
	if(flag,
		if(p==q,
			matrix(1,2,i,j,if(j==1,p,2))
		,
			[p,1;q,1]
		)
	,
		p*q
	)
};
addhelp(rsp, "rsp(b, {flag=0}): Generates a random b-bit semiprime. If flag is nonzero, returns the factorization of the number.");

[CRGreathouse]

Originally Posted by science_man_88

doesn't 3 depend on 2 ?

It doesn't have to. Suppose your program works like this:

foo(name, description)={
  \\ stuff goes here that figures out what the user wants
  if (userDesire == 1,
    print("forprime(p="start","stop","func");")
    return;
  );
  if (userDesire == 2,
    print("isprime("start");")
    return;
  );
  if (userDesire == 3,
    error("i'm afraid I can't do that, Dave.")
  );
  error("Bad user desire code")
};

You could work out code that goes in the blocks above, even without filling in the part with the comment. Of course you could only use it by calling those functions you create directly...

[science_man_88]

interesting idea...

dictionary for step 2 with different wordings leading to a main math word that they describe.

that math word can be linked to specific codes to help put it in practice.

[CRGreathouse]

Originally Posted by science_man_88

interesting idea...

dictionary for step 2 with different wordings leading to a main math word that they describe.

that math word can be linked to specific codes to help put it in practice.

Right. I would put each of them in its own function and document what the function does. If you ever got a natural language processor working, you can have it read the addhelp statements to determine which one is appropriate to use.