 mersenneforum.org a new Deterministic primality testing
 Register FAQ Search Today's Posts Mark Forums Read  2012-12-07, 07:43   #23
LaurV
Romulan Interpreter

Jun 2011
Thailand

22·3·739 Posts Quote:
 Originally Posted by LaurV It turned out there is no big deal to implement this. No idea if pari has one already.
Well, I just figured out that the a t_COMPLEX type in pari accepts coefficients of the t_MOD type. This voids the requirement for a function, as one can define "base=Mod(3,n)+Mod(2,n)*I" for a given n, then pari takes care by itself to do modular things with the coefficients. Although not so fast like my last implementation, it is however much faster then the initial version, and it would allow somebody to test by himself, using nothing except pari default functions and types (no "unknown" complex_pow_mod function).

So, one can modify the forstep parameters to go as high as he likes, eventually going 4 by 4 to be faster, and/or cancelling 5+12i test (I use the step 2 by 2 and testing both cases to show that the thing is working, you can also remove the primality test and it will print primes, or use ispseudoprime(n,1) to make it much faster, but here be careful that you can lose solutions if the random base for RM test is unlucky selected).

Code:
gp > nr=0; cnt=0; forstep(n=11,10^7,2,if(((z=(Mod(3,n)+Mod(2,n)*I)^(n+1))==13||z==5+12*I)&&!isprime(n),nr++; print(n" : "n%4"     ")); if(n
>cnt,cnt+=10^6; printf("...%d...%c",n,13))); nr
1105 : 1
2465 : 1
10585 : 1
29341 : 1
...<snip many lines deleted>...
9131401 : 1
9638785 : 1
9890881 : 1
%6 = 69
gp >
There should be no counterexample 3 (mod 4) to 10^9.   2012-12-07, 11:45 #24 fivemack (loop (#_fork))   Feb 2006 Cambridge, England 11000101100102 Posts random thoughts comprised entirely of inutility My suspicion is that the '==3 mod 4' part means that counterexamples are large because they have to be a product of three primes ==3 mod 4. Looking at the way that pseudoprimes work in base 2: Code: for k in [1000000..2000000] do b:=IntegerRing(k)!2; t:=b^k; if (t eq 2 and not IsPrime(k)) then print k, Factorisation(k); for j in PrimeDivisors(k) do print " ",j,Order(FiniteField(j)!2); end for; end if; end for; eg 251*4051 is a base-2 pseudoprime because the order of 2 mod 251 and mod 4051 are both 50, and 50 divides 251*4051-1. what happens if you look at products of three primes-congruent-to-3-mod-4 where (3+2i) has small order mod each p_i? Code: TT:=[]; S:=-1; for t in [1..200000] do S:=4+S; while (not IsPrime(S)) do S:=4+S; end while; Q:=FiniteField(S^2); QQ:=S^2-1; i:=Sqrt(Q!-1); if (Order(3+2*i) lt 30*QQ/S) then print S,QQ/Order(3+2*i),Factorisation(Order(3+2*i)); Append(~TT,S); end if; end for; print TT; P:=PolynomialRing(Integers()); print "begin"; for a in TT do for b in TT do for c in TT do if (a gt b and b gt c) then So:=a*b*c; S:=IntegerRing(So); Sx:=PolynomialRing(S); Sx1:=quo; k:=Coefficient((3+2*q)^So,0); if (k lt 10000 or k gt So-10000) then print a,b,c,So, k; end if; end if; end for; end for; end for; print "end"; (http://magma.maths.usyd.edu.au/calc/)   2012-12-07, 12:00 #25 fivemack (loop (#_fork))   Feb 2006 Cambridge, England 11000101100102 Posts hmm, this is possibly quite an interesting additional question: How big a set of 4k+3-primes can you find where 3+2i has the same order mod each prime? How about the same odd-part-of-order? The birthday paradox isn't really on our side because the orders are around-p^2 rather than around-p. think of something like 1011863 990288 23 [ <47, 1>, <21529, 1> ] 47 23 43994 43056 21529 23 43994 43056 1012441 1008000 120 [ <241, 1>, <4201, 1> ] 241 120 8437 8400 4201 120 8437 8400 base-53 pseudoprimes the top lines are N, phi(N), order of 53 mod N, factorisation of N the indented lines are p, O=order of 53 mod p, (N-1)/O, phi(N)/O so having two primes where 53 has the same order was at least a good start   2012-12-07, 16:01 #26 fivemack (loop (#_fork))   Feb 2006 Cambridge, England 2×29×109 Posts ... ok, so the numbers where the order of 2 mod p is 47 are 2351 and 4513, which are among the factors of 2^47-1. So maybe we want to be looking at the factorisation into primes of Z[i] of (3+2*i)^k-1. But, hmm, it looks as if the norms of such numbers with k prime only have prime factors which are congruent to 1 mod 4 ... so we're getting 'accidental' factors for composite k, and they're a lot rarer and a lot smaller. Last fiddled with by fivemack on 2012-12-12 at 14:48   2012-12-08, 11:22 #27 LaurV Romulan Interpreter   Jun 2011 Thailand 22×3×739 Posts There are no counterexample 3 (mod 4) for b=3+2i, up to n=10^10 (and a bit upper). I stoped it.   2012-12-10, 02:45 #28 wsc812   Dec 2012 China 1110 Posts how to prove has no Positive integer root, is variable , is constant and are parameter ,and all character represents Positive integer.it's a question about the conjecture. my proof on mathoverflow : http://mathoverflow.net/questions/11...ese-conditions Last fiddled with by wsc812 on 2012-12-10 at 02:54   2012-12-10, 18:45 #29 JFranke   Nov 2012 Bonn University 23 Posts Pomerance's reasoning for BPSW works here as well I think Alex Kruppa is correct about this being essentially a combination of a (p-1) and a (p+1)-test. Moreover, the examples (if any) constructed by C. Pomerance's heuristic are all expamples of pseudoprimes for the test considered in this thread.   2012-12-11, 02:51   #30
ixfd64
Bemusing Prompter

"Danny"
Dec 2002
California

230810 Posts Quote:
 Originally Posted by JFranke I think Alex Kruppa is correct about this being essentially a combination of a (p-1) and a (p+1)-test. Moreover, the examples (if any) constructed by C. Pomerance's heuristic are all expamples of pseudoprimes for the test considered in this thread.
I see you've finally registered here. Welcome!   2012-12-11, 09:16 #31 akruppa   "Nancy" Aug 2002 Alexandria 25×7×11 Posts Welcome on mersenneforum, Jens!   2012-12-13, 10:18 #32 wsc812   Dec 2012 China 11 Posts I have found the Complete proof for N=4k+3!!!!!   2012-12-13, 13:32   #33
Uncwilly
6809 > 6502

"""""""""""""""""""
Aug 2003
101×103 Posts

210318 Posts Quote:
 Originally Posted by wsc812 I have found the Complete proof for N=4k+3!!!!!
Big blue letters means it must be true.   Thread Tools Show Printable Version Email this Page Similar Threads Thread Thread Starter Forum Replies Last Post a1call Miscellaneous Math 194 2018-03-19 05:54 lukerichards Software 8 2018-01-24 22:30 1260 Software 17 2015-08-28 01:35 CRGreathouse Computer Science & Computational Number Theory 18 2013-06-08 19:12 jasong Math 1 2007-11-06 21:46

All times are UTC. The time now is 22:44.

Sat Oct 24 22:44:27 UTC 2020 up 44 days, 19:55, 2 users, load averages: 1.94, 1.73, 1.84