Por favor, ayúdenme a entender los signos matemáticos en el paso polinómico de la criba cuadrática de autoinicialización

Question

Para poder revisar mi implementación de la Criba Cuadrática de Polinomios Múltiples en la Criba Cuadrática Autoinicializada, necesito ayuda con algunos símbolos matemáticos.

Estoy tratando de seguir Scott Contini's en Self Initializing Quadratic Sieve, donde da un excelente resumen de los pasos necesarios en la imagen de abajo (Fig. 2.3). Por favor, ayúdame a entender todos los símbolos matemáticos allí.

1. ¿Qué es? $tmem_p$ ?
2. ¿Qué es el signo "x"?
3. ¿Qué es el signo "/"?
4. ¿Qué es la "ainv"?
5. ¿Qué es el signo "#"?
6. ¿Qué es el signo "||"?
7. ¿Qué es? $soln1_p$ ?

---

Answer 1

Dado que has implementado el algoritmo MPQS, intentaré responder de forma concisa a cada uno de los puntos "¿Qué es...?". Algunos de ellos son efectivamente "signos matemáticos", pero otros son más bien nombres de variables, etc.

Cuando el tiempo lo permita, espero volver a relacionar mis respuestas con las motivaciones operativas, es decir, cómo SIQS revisa el paso de inicialización de MPQS.

1. ¿Qué es? $\mathit{tmem}_p$ ?
2. ¿Qué es el " $\times$ "signo"
3. ¿Qué es el signo "/"?

Esta notación aparece en la citada "Figura 2.3: resumen de las etapas de inicialización de siqs" en la página 14 de la tesis de máster de Contini. Es la primera declaración dentro de un bucle en $\ell = 1 \text{ to } s$ :

Calcula $\gamma = \mathit{tmem}_p \times (a/q_\ell)^{-1} \bmod q_\ell$ .

Una declaración más clara se encuentra en el Prime Wiki para el tamiz cuadrático autoinicializado en la sección "Generación del primer polinomio".

El primer término $\mathit{tmem}_p$ es una matriz previamente rellenada con entradas para cada primo $p$ en la base del factor. Volviendo a la "Figura 2.2: resumen del algoritmo mpqs" (en la página 13), encontramos allí (bajo Calcular los datos de puesta en marcha ) que para cada primo $p$ almacenamos una raíz cuadrada modular de $N \bmod p$ es decir, una solución $t$ de:

$$t^2 \equiv N \bmod p$$

donde $N$ es el entero compuesto (no una potencia pura) que hay que factorizar. Nótese que en este esquema de cribado sólo nos interesará una base factorial cuyos primos $p$ tienen $N$ como un residuo cuadrático. Las entradas de la configuración $\mathit{tmem}_p$ son "realizaciones" de esa propiedad.

Pero la notación es, en el mejor de los casos, confusa y podría decirse que se trata de una pequeña errata. La expresión del array $\mathit{tmem}_p$ necesita un índice (o desplazamiento) para denotar que raíz cuadrada modular de $N$ se pretende. Desde el hecho de que "computamos" $\bmod q_\ell$ podemos deducir que el $\mathit{tmem}_p$ entrada para prime $q_\ell$ es necesario en esta expresión.

A continuación el cartel " $\times$ " es sólo la multiplicación, aquí la multiplicación modular $\bmod q_\ell$ .

También el signo "/" puede entenderse como una división entera ordinaria, teniendo en cuenta la advertencia: aquí $a$ es el producto sobre algunos primos que incluyen $q_\ell$ . Así que la división de enteros es exacta, y el cociente $(a/q_\ell)$ podría ser también proporcionada multiplicando juntos todos esos primos excepto omitiendo el particular $q_\ell$ designado por el índice del bucle $\ell$ (pasando de $1$ a $s$ (sea cual sea el paso del bucle en el que nos encontremos).

4. ¿Qué es la "ainv"?

En realidad se trata de una matriz $\mathit{ainv}_p$ en el siguiente bloque del algoritmo. Para cada factor base primo $p$ que no dividir $a$ (es decir, aquellos primos de base factorial que fueron no multiplicado para obtener $a$ ), calculamos la inversa multiplicativa de $a \bmod p$ :

Calcula $\mathit{ainv}_p = a^{-1} \bmod p$

El cálculo de la inversa multiplicativa de $a$ con respecto al módulo coprimo $p$ es un algoritmo de división conocido ejercicio.

5. ¿Qué es el signo "#"?

Cuando esto aparece en la siguiente sección Etapa de inicialización para el siguiente $2^{s-1}-1$ polinomios El símbolo de la libra es simplemente una abreviatura de "numerado". Es decir, esa frase parentética inicial debe entenderse como que dice:

(Supongamos que acabamos de tamizar el polinomio numerado $i$ , por lo que estamos inicializando el polinomio numerado $(i+1)$ , $1\le i \le 2^{s-1} - 1$ )

En otras palabras, se trata más bien de una abreviatura para pasar a la siguiente numerado polinomio en lugar de una notación matemática de algún tipo. La "numeración" subyacente de los polinomios está relacionada matemáticamente con un código Gray, para el que véase el Apéndice C del artículo de Contini.

6. ¿Qué es el " $||$ ¿"Signo"?

Esta es quizás la menos estándar de las notaciones empleadas aquí. Aparece como:

Dejemos que $\nu$ sea el número entero que satisface $2^\nu || 2i$ .

En otras palabras, esto significa $\nu$ es la mayor potencia de $2$ que divide $2i$ .

7. ¿Qué es? $\mathit{soln}1_p$ ?

Esta notación $\mathit{soln}1_p$ es un nombre de variable para una matriz de valores, una entrada por cada factor base primo $p$ que no dividir $a$ . Sus valores se definen (como también $\mathit{soln}2_p$ voluntad) para el primer polinomio y posteriormente actualizado en serie para el siguientes polinomios .