149 lines
4.7 KiB
Markdown
149 lines
4.7 KiB
Markdown
---
|
|
id: 598eea87e5cf4b116c3ff81a
|
|
title: I fattori di un numero di Mersenne
|
|
challengeType: 5
|
|
forumTopicId: 302264
|
|
dashedName: factors-of-a-mersenne-number
|
|
---
|
|
|
|
# --description--
|
|
|
|
Un numero di Mersenne è un numero nella forma di <code>2<sup>P</sup>-1</code>.
|
|
|
|
Se `P` è primo, il numero di Mersenne può essere un primo di Mersenne. (Se `P` non è primo, anche il numero di Mersenne non è primo.)
|
|
|
|
Nella ricerca di numeri primari di Mersenne è vantaggioso eliminare gli esponenti trovando un piccolo fattore prima di iniziare un potenzialmente lungo [test di Lucas-Lehmer](https://rosettacode.org/wiki/Lucas-Lehmer test "Lucas-Lehmer test").
|
|
|
|
Ci sono algoritmi molto efficienti per determinare se un numero divide <code>2<sup>P</sup>-1</code> (o equivalentemente, se <code>2<sup>P</sup> mod (il numero) = 1</code>).
|
|
|
|
Alcuni linguaggi hanno già implementazioni integrate di questa operazione esponente-e-modulo (chiamata modPow o simile).
|
|
|
|
Ecco come puoi implementare questo modPow:
|
|
|
|
Ad esempio, calcoliamo <code>2<sup>23</sup> mod 47</code>.
|
|
|
|
Converti l'esponente 23 in binario, ottenendo 10111. A partire da <code><tt>square</tt> = 1</code>, fai ripetutamente il quadrato.
|
|
|
|
Rimuovi il bit superiore dell'esponente, e se è 1 moltiplica `square` per la base dell'esponenziazione (2), poi calcola <code><tt>square</tt> modulo 47</code>.
|
|
|
|
Usa il risultato del modulo dall'ultimo passo come valore iniziale dello `square` nella fase successiva:
|
|
|
|
<pre>Remove Optional
|
|
square top bit multiply by 2 mod 47
|
|
------------ ------- ------------- ------
|
|
1*1 = 1 1 0111 1*2 = 2 2
|
|
2*2 = 4 0 111 no 4
|
|
4*4 = 16 1 11 16*2 = 32 32
|
|
32*32 = 1024 1 1 1024*2 = 2048 27
|
|
27*27 = 729 1 729*2 = 1458 1
|
|
</pre>
|
|
|
|
Dal momento che <code>2<sup>23</sup> mod 47 = 1</code>, 47 è un fattore di <code>2<sup>P</sup>-1</code>.
|
|
|
|
(Per vedere questo, sottrai 1 da entrambi i lati: <code>2<sup>23</sup>-1 = 0 mod 47</code>.)
|
|
|
|
Dal momento che abbiamo dimostrato che 47 è un fattore, <code>2<sup>23</sup>-1</code> non è primo.
|
|
|
|
Ulteriori proprietà dei numeri di Mersenne ci permettono di affinare il processo ancora di più.
|
|
|
|
Qualsiasi fattore `q` di <code>2<sup>P</sup>-1</code> deve essere modulo `2kP+1`, essendo `k` un numero intero positivo o uguale a zero. Inoltre, `q` deve essere `1` o `7 mod 8`.
|
|
|
|
Infine qualsiasi fattore potenziale `q` deve essere [primo](https://rosettacode.org/wiki/Primality by Trial Division "Primality by Trial Division").
|
|
|
|
Come in altri algoritmi di divisione di prova, l'algoritmo si ferma quando `2kP+1 > sqrt(N)`. Questi test funzionano principalmente solo su numeri Mersenne dove `P` è primo. Ad esempio, <code>M<sub>4</sub>=15</code> non produce fattori che utilizzano queste tecniche, ma fattori in 3 e 5, nessuno dei quali nella forma `2kP+1`.
|
|
|
|
# --instructions--
|
|
|
|
Utilizzando il metodo sopra descritto trovare un fattore di <code>2<sup>p</sup>-1</code>.
|
|
|
|
# --hints--
|
|
|
|
`check_mersenne` dovrebbe essere una funzione.
|
|
|
|
```js
|
|
assert(typeof check_mersenne === 'function');
|
|
```
|
|
|
|
`check_mersenne(3)` dovrebbe restituire una stringa.
|
|
|
|
```js
|
|
assert(typeof check_mersenne(3) == 'string');
|
|
```
|
|
|
|
`check_mersenne(3)` dovrebbe restituire la stringa `M3 = 2^3-1 is prime`.
|
|
|
|
```js
|
|
assert.equal(check_mersenne(3), 'M3 = 2^3-1 is prime');
|
|
```
|
|
|
|
`check_mersenne(23)` dovrebbe restituire la stringa `M23 = 2^23-1 is composite with factor 47`.
|
|
|
|
```js
|
|
assert.equal(check_mersenne(23), 'M23 = 2^23-1 is composite with factor 47');
|
|
```
|
|
|
|
`check_mersenne(929)` dovrebbe restituire la stringa `M929 = 2^929-1 is composite with factor 13007`.
|
|
|
|
```js
|
|
assert.equal(
|
|
check_mersenne(929),
|
|
'M929 = 2^929-1 is composite with factor 13007'
|
|
);
|
|
```
|
|
|
|
# --seed--
|
|
|
|
## --seed-contents--
|
|
|
|
```js
|
|
function check_mersenne(p) {
|
|
|
|
}
|
|
```
|
|
|
|
# --solutions--
|
|
|
|
```js
|
|
function check_mersenne(p){
|
|
function isPrime(value){
|
|
for (let i=2; i < value; i++){
|
|
if (value % i == 0){
|
|
return false;
|
|
}
|
|
if (value % i != 0){
|
|
return true;
|
|
}
|
|
}
|
|
}
|
|
|
|
function trial_factor(base, exp, mod){
|
|
let square, bits;
|
|
square = 1;
|
|
bits = exp.toString(2).split('');
|
|
for (let i=0,ln=bits.length; i<ln; i++){
|
|
square = Math.pow(square, 2) * (bits[i] == 1 ? base : 1) % mod;
|
|
}
|
|
return (square == 1);
|
|
}
|
|
|
|
function mersenne_factor(p){
|
|
let limit, k, q;
|
|
limit = Math.sqrt(Math.pow(2,p) - 1);
|
|
k = 1;
|
|
while ((2*k*p - 1) < limit){
|
|
q = 2*k*p + 1;
|
|
if (isPrime(q) && (q % 8 == 1 || q % 8 == 7) && trial_factor(2,p,q)){
|
|
return q; // q is a factor of 2**p-1
|
|
}
|
|
k++;
|
|
}
|
|
return null;
|
|
}
|
|
let f, result;
|
|
result="M"+p+" = 2^"+p+"-1 is ";
|
|
f = mersenne_factor(p);
|
|
result+=f == null ? "prime" : "composite with factor "+f;
|
|
return result;
|
|
}
|
|
```
|