La factorisation des nombres

En mathématique, factoriser un nombre consiste à le décomposer sous la forme d'un produit de plusieurs nombres. Par exemple, on peut factoriser $15$ de la manière suivante:

$$15 = 1 \cdot 3 \cdot 5$$

La factorisation des nombres permet de simplifier des expressions en mettant en évidence des facteurs communs et elle est également au coeur de l'algorithme de chiffrement RSA.

Si les nombres qui composent le produit sont des nombres premiers, alors on parle de factorisation entière en nombres premiers ou décomposition en produit de facteurs premiers.

Si la seule factorisation possible d'un nombre $N$ ne donne que deux nombres distincts : $1$ et $N$ lui même, alors on dit que $N$ est un nombre premier.

Nous souhaitons écrire un programme qui affiche tous les facteurs premiers d'un nombre donnée $N$.

Exercices

Exercice 1

Ecrivez un tel programme est testez-le:

Solution

fun printDivisors(x: Long) {
    var x: Long = x
    var d: Long = 2
    println(1)
    while (x != 1L) {
        if (x % d == 0L) {
            println(d)
            x = x / d
        } else {
            d = d + 1
        }
    }
}

Exercice 2

Quels sont les facteurs du nombre $14817181051$:

Solution

$14817181051 = 1 \cdot 121531 \cdot 121921$

Exercice 3 (supplément)

Implémentez la fonction pour traiter les nombres vraiment très grands ($x \ge 2^{63}$).

Solution

fun printDivisors(x: String) {
    var x = BigInteger(x)
    var d = BigInteger.valueOf(2)
    println(BigInteger.ONE)
    while (! x.equals(BigInteger.ONE)) {
        if (x.mod(d).equals(BigInteger.ZERO)) {
            println(d)
            x = x.divide(d)
        } else {
            d = d.add(BigInteger.ONE)
        }
    }
}

Exercice 4

"Craquer" une clé privée RSA consiste à factoriser un nombre vraiment très très grand. Du genre:

8294223333 7656026686 2329482315 6646778935 9867857362 2044308600 9678903390 4746132885 8167435767 4041598290 5219501287 7461374753 2365906767 4241767522 5470968046 7038319702 3712583678 5380551488 8183561060 0345974701 9017501185 6788930077 1291963349 2419981471 4859043255 4434548240 5786613459 5910926155 1083888709 5538409933 5443173581 0719564851 6400846368 5064925362 8158364931 1221352141 6206848579 2793023877 5273648681 7959589451 7027641021 8491625862 5456905228 0834748353 2989960322 1060610910 1649515224 3753280314 7467264406 8989742688 2458671700 5680147499 1162946682 7969282900 1997224442 5653127734 3561805896 1179088785 3736593621 7152004854 8241781423 8098608199 4303754706 0657641768 0859960268 4019003764 4066888437 8433901101 0192624133 6881066583 1296779490 5613428682 7509727060 1554044731 1886076201 7852885515 7641443776 2907110695 3898344794 7770909904 0747378502 6123841899 9606031155 6731885298 6723158324 1899232898 4443950947 8009603997 1611096699 8305158818 0252295144 1790739005 4932836592 8523046161 3237244729 2680570279 2178699724 8968651115 3524328591 2211438569 0077192644 3728642557 4561677418 2209667291 7355931672 1335203581 6758009834 0641778303 1661083208 8077696087 8525170170 7186769311 6940964666 3883321337 1030766193 2895165033 9607854692 1979465281 5948123557 0455980228 4813293865 4483177163 4853191872 9400689308 1254082695 2630324397 2668656079 5574877101 7506889931 8859449890 8994726487 9703373565 3995737477 4460084793 8309894969 7006863437 8405143460 3719040114 7428779420 1124775729 6650448638 9692297135 8806360401 7460361673 4562329022 9523181946 3310621314 7749426629 3761738399 2064770178 7241158673 7633125074 2974379790 1811990415 0393060806 2819963376 9283843352 3696151970 0962631999 7329011219 1185648930 8801160711 0327614903 1241777468 8469123985 4410933562 8276780989 4054564700 7533186364 6115033719 6837906340 6160826689 9358562450 1098109994 4439805273 4304589927 2110629478 5709245778 3665285080 2238278890 5212013548 0662609569 5584146899 8408586270 6640653074 0894030485 3579971327 3793529366 4795744067 1630173058 4456619105 9333470340 0485041813 3716670717 3439104589 6929568824 0614685051 1768957341 4035701602 3494146096 1105971538 2689366665 8928878892 0363562418 6081027494 9798502967 2806622733 6385877284 7130137452 0625068304 0208263854 3067205261 1145155415 3657948539 1849590668 7823586629 3651018712 5135111727 1901457158 5942620384 9191014514 3158356012 6462153994 0732760801 2466159150 5383438871 9125926746 0929718576 9236069325 3973787116 5790947398 9349446054 0943594502 3180136717 6719242658 0167455824 0542064614 1452712346 9585116939 7013643506 3520841220 3053038546 2175581124 5370458035 1584361254 9364058916 951599.

Si vous arrivez à trouver les deux nombres premiers qui factorisent le nombre ci-dessus, je vous prédit un avenir radieux!