mersenneforum.org  

Go Back   mersenneforum.org > Math Stuff > Computer Science & Computational Number Theory

Reply
 
Thread Tools
Old 2012-12-07, 07:43   #23
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
Jun 2011
Thailand

22·3·739 Posts
Default

Quote:
Originally Posted by LaurV View Post
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.
LaurV is offline   Reply With Quote
Old 2012-12-07, 11:45   #24
fivemack
(loop (#_fork))
 
fivemack's Avatar
 
Feb 2006
Cambridge, England

2×29×109 Posts
Default 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<x>:=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<x>:=PolynomialRing(S);
Sx1<q>:=quo<Sx|x^2+1>;
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/)
fivemack is offline   Reply With Quote
Old 2012-12-07, 12:00   #25
fivemack
(loop (#_fork))
 
fivemack's Avatar
 
Feb 2006
Cambridge, England

11000101100102 Posts
Default

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
fivemack is offline   Reply With Quote
Old 2012-12-07, 16:01   #26
fivemack
(loop (#_fork))
 
fivemack's Avatar
 
Feb 2006
Cambridge, England

2·29·109 Posts
Default

... 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
fivemack is offline   Reply With Quote
Old 2012-12-08, 11:22   #27
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
Jun 2011
Thailand

22·3·739 Posts
Default

There are no counterexample 3 (mod 4) for b=3+2i, up to n=10^10 (and a bit upper).
I stoped it.
LaurV is offline   Reply With Quote
Old 2012-12-10, 02:45   #28
wsc812
 
Dec 2012
China

B16 Posts
Default

how to prove q_1t^3+(k_2-1)t^2-k_2((q_1^2-1)k_1+1)^2=0 has no Positive integer root, t is variable ,q_1 is constant and k_1,k_2 are parameter
q_1>0,k_1>0,k_2>0 ,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
wsc812 is offline   Reply With Quote
Old 2012-12-10, 18:45   #29
JFranke
 
JFranke's Avatar
 
Nov 2012
Bonn University

108 Posts
Default 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.
JFranke is offline   Reply With Quote
Old 2012-12-11, 02:51   #30
ixfd64
Bemusing Prompter
 
ixfd64's Avatar
 
"Danny"
Dec 2002
California

44048 Posts
Default

Quote:
Originally Posted by JFranke View Post
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!
ixfd64 is online now   Reply With Quote
Old 2012-12-11, 09:16   #31
akruppa
 
akruppa's Avatar
 
"Nancy"
Aug 2002
Alexandria

1001101000002 Posts
Default

Welcome on mersenneforum, Jens!
akruppa is offline   Reply With Quote
Old 2012-12-13, 10:18   #32
wsc812
 
Dec 2012
China

11 Posts
Default

I have found the
Complete proof for N=4k+3!!!!!
wsc812 is offline   Reply With Quote
Old 2012-12-13, 13:32   #33
Uncwilly
6809 > 6502
 
Uncwilly's Avatar
 
"""""""""""""""""""
Aug 2003
101×103 Posts

221D16 Posts
Default

Quote:
Originally Posted by wsc812 View Post
I have found the Complete proof for N=4k+3!!!!!
Big blue letters means it must be true.
Uncwilly is online now   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
A Theoretical (vs. Proficient/Practical) Deterministic Primality Test a1call Miscellaneous Math 194 2018-03-19 05:54
Primality testing non-Mersennes lukerichards Software 8 2018-01-24 22:30
Testing an expression for primality 1260 Software 17 2015-08-28 01:35
Testing Mersenne cofactors for primality? CRGreathouse Computer Science & Computational Number Theory 18 2013-06-08 19:12
a new primality testing method jasong Math 1 2007-11-06 21:46

All times are UTC. The time now is 19:21.

Sun Oct 25 19:21:35 UTC 2020 up 45 days, 16:32, 0 users, load averages: 2.01, 1.71, 1.70

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.