13 votos

Encontrar un número compuesto nn satisface (2+3I)n23I(modn)(2+3I)n23I(modn)

Como sabemos si pp es un número primo impar, a continuación, (a+bI)pa+(1)p12bI(modp),(a+bI)pa+(1)p12bI(modp), donde I=1I=1. Sin embargo, hay cualquier número compuesto nn que satisface (2+3I)n23I(modn)?(2+3I)n23I(modn)?nn es una solución para la ecuación de 13n11(modn)13n11(modn), pero no puede seguir así.

Muchas gracias de antemano.

8voto

Al C Puntos 1194

There is no such n1010There is no such n1010

When doing a brute-force numerical search on this problem, there are two obvious modes of attack.

One method is to compute (2+3I)n  nN(2+3I)n  nN iteratively via (2+3I)n=(2+3I)(2+3I)n1(2+3I)n=(2+3I)(2+3I)n1, and only reduce modnmodn to check the congruence for each nn. (2+3I)n(2+3I)n has O(n)O(n) digits, so each multiply takes O(n)O(n) time. Doing NN such multiplies brings the overall complexity to O(N2)O(N2).

A more efficient algorithm is to compute (2+3I)n (mod n)(2+3I)n (mod n) separately for each nn using e.g. a binary ladder, reducing modnmodn at each stage of the binary ladder. Checking a single nn takes log(n)log(n) this with approach, resulting in a total time complexity of O(NlogN)O(NlogN) to check all nNnN.

The complexity arguments given above are only estimates. However, I implemented both algorithms and found that they are borne out in practice: the two algorithms both take ~3s to check all n105n105 using one core on my system. From that point on, the first algorithm takes roughly quadratic time, whereas the second one takes roughly linear time.

Here is my implementation in PARI/GP of the faster of the two algorithms:

\\ Our search range
NMIN=2;
NMAX=100000000;


\\ Computes x^y (mod n) using a binary ladder
\\ This is Algorithm 9.3.1 from Crandall and Pomerance, "Prime Numbers", 2 Ed.
\\ RETURNS x (RATHER THAN 1) IF y=0...
pow_modN(x,y,n)={
  \\ Get: 1) y_binary (the binary expansion of y)
  \\      2) D        (the number of bits in y_binary)
  \\         Unfortunately these are not interleaved!
  y_binary = binary(y);
  y_shl_D=y;
  D=0;
  while(y_shl_D,
    D++;
    y_shl_D>>=1;
  );

  \\ Initialize to z=x.
  \\ Loop over bits of y, starting with the next-to-highest
  \\ y_binary[1] is the MSB, y_binary[D] is LSB.
  z=x;
  for(j=2, D,
    z*=z;
    if(y_binary[j], z*=x);
    z%=n;
  );

  \\ Return z=x^y (mod n)
  z;
}


\\ We work in the field of Gaussian integers, Z(w) here w==I==sqrt(-1).
w=quadgen(-4);

\\ We intend to exponentiate a.
a = 2+3*w;

\\ Compute a^n for all n in [NMIN,NMAX]
for(n=NMIN, NMAX, {
  zPowN_modN = pow_modN(a, n, n);
  re_zPowN_modN = real(zPowN_modN);
  im_zPowN_modN = imag(zPowN_modN);

  if(re_zPowN_modN-2,,
    if(im_zPowN_modN-n+3,,
      if(isprime(n),,
        print(n);
      );
    );
  );

  if(n%100000,,printf("Done to %u\n", n));

});

quit;

Negative results with numerical searches like this one are dangerous, because many different errors would produce the same result. For example, in C, (-1)%4 == 3%4 evaluates to -1==3 which is false, despite the fact that 13 (mod 4)13 (mod 4). To get the desired result, one has to check (-1-3)%4==0, which returns true. Considering this, double checks are necessary.

For the above code I checked the result in two ways. Firstly, I dropped the requirement that nn be composite, which results in a long list of primes n=3,7,11,19,23,n=3,7,11,19,23, I redid this calculation with a different algorithm (the "first algorithm above"), different software (Maple) and different hardware (my laptop), and compared the resulting lists up to 106106, with no differences found.

My second double check was to make a minor modification to the above code to check the congruence (2+3I)n2+3I (mod n)(2+3I)n2+3I (mod n) for composite $$ n. Este rápidamente se entera de que muchas de las soluciones: 1105, 2465, 10585, 29341, 41041, 46657, 115921, 162401, , lo cual está de acuerdo con la lista dada por Zev Chonoles en los comentarios.

3voto

Zander Puntos 8843

He logrado con nada concluyente, pero aquí están algunas de las notas que se espera que puedan ser fuente de inspiración.

1. Dudo que esto es conocido como verdadero, ya que si se cumple, se da una rápida definitiva primalidad de verificación de números de la forma 4k+34k+3. Entonces, por ejemplo, el probable primer registros no se han de incluir cualquiera de estos números en la lista, por lo que "nadie sabe cómo demostrar o refutar ... primalidad." (Ya he comprobado dos de ellos.)

2. Si p1(mod4)p1(mod4)(2+3i)p11(modp)(2+3i)p11(modp). Si hay alguna k<p1k<p1 tal que (2+3i)k23i(modp)(2+3i)k23i(modp) (2+3i)k+113(modp)(2+3i)k+113(modp) y teniendo en cuenta las normas 13k13(modp)(2+3i)(k+1)(k1)1(modp) Me gustaría general de la regla de este caso, pero no puedo, ya que mantiene para k=19,p=61.

Si no k, p no se puede dividir n, por lo que parece prudente concentrarse en sólo números divisibles por los números primos que son 3 modulo 4.

3. Si p3(mod4) (2+3i)p211(modp) y podemos encontrar una solución si np(modp21). En particular, no será una solución con n=p3 si 13p11(modp3). Yo no era capaz de encontrar cualquier prime, pero sospecho que no puede ser descartado por ejemplo, con Hensel del lexema, ya que hay soluciones a 13p11(modp2) (por ejemplo,p=863).

4. Generalizar a partir de 3, sería suficiente para encontrar n un producto de números primos que son 3 mod 4 tales que para cada uno de los prime p dividiendo n np1(modp21) Si n es un producto de distintos números primos, entonces todos se deben satisfacer p3<n y por lo tanto no debe ser de al menos 4.

i-Ciencias.com

I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.

Powered by:

X