Facteur entier tweetable le plus rapide

17

La tâche consiste à trouver un facteur non trivial d'un nombre composite.

Écrivez le code qui trouve le plus rapidement possible un facteur non trivial d'un nombre composite, sous réserve que votre code ne dépasse pas 140 octets. La sortie doit simplement être le facteur que vous avez trouvé.

Votre code peut prendre des entrées et donner des sorties de n'importe quelle manière, y compris par exemple en tant qu'arguments à une fonction.

Cas de test qui répertorient tous les facteurs (il vous suffit d'en générer un)

187: 11 17
1679: 23 73
14369648346682547857: 1500450271 9576890767
34747575467581863011: 3628273133 9576890767
52634041113150420921061348357: 2860486313 5463458053 3367900313
82312263010898855308580978867: 264575131106459 311111111111113
205255454905325730631914319249: 2860486313 71755440315342536873 
1233457775854251160763811229216063007: 1110111110111 1000000000063 1111111999999
1751952685614616185916001760791655006749: 36413321723440003717 48112959837082048697

Je ne marquerai pas votre réponse sur le cas de test difficile suivant qui peut être intéressant pour le test:

513231721363284898797712130584280850383: 40206835204840513073 12764787846358441471

But

Votre score est le temps combiné pour factoriser tous les cas de test ci-dessus avec une pénalité de 10 minutes pour chaque factorisation échouée (tous arrondis à la seconde la plus proche). Votre code devrait également fonctionner pour d'autres entiers, c'est-à-dire ne devrait pas simplement coder en dur ces réponses.

Je vais arrêter votre code après 10 minutes.

Si deux personnes obtiennent le même score, la première réponse l'emporte.

Restrictions

Votre code ne peut pas utiliser de fonction intégrée ou de bibliothèque qui effectue une factorisation entière. Vous pouvez supposer que l'entrée prend moins de 256 bits. Tous les numéros d'entrée seront composites.

Comment vais-je chronométrer?

Je vais littéralement fonctionner time ./myprogsur mon système Ubuntu pour faire le chronométrage, veuillez donc également fournir un programme complet à exécuter pour moi qui inclut toute fonction que vous avez définie.

Une note pour les langues compilées

Le temps de compilation ne doit pas prendre plus d'une minute sur ma machine.

Est-ce réellement possible?

Si vous ignorez les contraintes d'espace, alors chacune peut être prise en compte en moins de 2 secondes sur mon ordinateur en utilisant du code Python + pypy pur.

Qu'est-ce qu'un algorithme d'affacturage non trivial?

L'algorithme rho de Pollard est rapide et adapté au golf. Bien sûr, il existe également de nombreuses autres façons de factoriser un entier .

Le tamis quadratique est encore plus rapide . Cela ressemble à un sérieux défi de le compresser en 140 octets.

Principaux scores

  • SEJPM , 10 minutes de pénalité pour le dernier cas de test + 16 secondes à Haskell

la source
Donc, on peut nous donner un nombre comme 2 ** 1024?
Conor O'Brien
@ ConorO'Brien Vous ne recevrez rien avec plus de chiffres que les cas de test.
Donc, en termes de précision, rien de plus que 256 bits.
Conor O'Brien
Pour une entrée comme 4, la sortie doit-elle être 2ou 2, 2?
M. Xcoder
1
@AndersKaseorg J'ai mis à jour la question suite à votre suggestion. Merci.

Réponses:

9

Haskell, 100 97 91 89 87 72 67 octets

Essayez-le en ligne!

-3 octets grâce à @flawr
-6 octets grâce à @flawr encore
-2 octets grâce à @flawr encore
-2 octets grâce à un ensemble optimisé de paramètres
-1 octet grâce à @flawrs encore une fois
-14 octets grâce à l'exigence d'avoir seulement à émettre un facteur
-5 octets grâce à @AndersKaseorg

f n|let s x=mod(x*x+7)n;a#b|d<-gcd(b-a)n,d>1=d|c<-s b=s a#s c=5#s 5

Cela fonctionne pour les 5 premiers cas de test en un temps inaperçu.
Cela expirera probablement sur le plus grand cas de test.

En général, cela renvoie généralement un facteur non trivial dans le temps proportionnel à la racine carrée du plus petit facteur.
Il ne fonctionnera pas sur chaque entrée car il ne fait pas varier le polynôme et la détection du cas exceptionnel est difficile à faire en 140 octets.
Il ne produira pas non plus la factorisation complète, mais plutôt un facteur non trivial et la division de l'entrée par ce facteur.
Il ne triera pas non plus les facteurs par taille.

La méthode utilisée est Pollard-Rho-Factoring avec la valeur de départ standard de 2 (avec le x^2+1polynôme standard appliqué une fois) et le facteur constant polynomial non standard de 7 (car cela 1n'a pas fonctionné avec 1679) pour toutes les évaluations ultérieures.

Programme complet ( factor.hs):

import System.Environment(getArgs)

f n|let s x=mod(x*x+7)n;a#b|d<-gcd(b-a)n,d>1=d|c<-s b=s a#s c=5#s 5

main= do
      args <- getArgs
      print$f (read $ head args :: Integer)

Compilez en tant que $ ghc factor.hs(besoins ghcinstallés).
Exécuter en tant que $ ./factor <number>.

Exemple d'exécution:

$ ./factor 187
11

Code non golfé:

f n=g 5 (s 5)
   where s x=mod(x*x+7)n
         g a b = if d>1 then d else g(s a)(s(s b))
               where d=gcd(b-a)n

Calcule le facteur non trivial en appelant gavec les valeurs initiales. Le polynôme est pré-appliqué sur 2 ici et ré-appliqué sur le résultat (5) afin que l'entrée de g(dans une clause "où" ) puisse toujours être facilement utilisée pour le test gcd. g(la version golfée utilise infixe #) essaie ensuite de calculer un facteur non trivial d(dans la clause where dans la version non golfée, en ligne dans la version golfée) comme la différence entre les deux entrées à g, si elle réussit, renvoie ledit facteur , sinon réessaie. Ici, il peut générer ncomme sortie si a==bet ne renvoie donc qu'un facteur trivial, l'approche appropriée pour gérer cela serait soit de faire varier les valeurs de départ lors de cet événement, soit de changer le polynôme.

SEJPM
la source
|1<2=s a#(s$s b) pourrait être remplacé par |c<-s b=s a#s c je pense :) (aussi: pourquoi ne postez-vous pas un lien TIO ?)
flawr
J'ai mis à jour la question suite aux suggestions de commentaires. Maintenant, vous n'avez besoin de produire qu'un seul facteur et les nombres sont garantis comme étant composites.
3
PS: pourquoi
jouons
4
Vous avez maintenant 53 octets pour implémenter un algorithme de factorisation encore plus sophistiqué :)
1
Vous pouvez également souscrire abs , car il best toujours non négatif. (Peut-être que vous vouliez dire abs$b-a, mais gcdacceptez des arguments négatifs et produit toujours un résultat non négatif.) Cela ramène cela à moins d'un demi-tweet!
Anders Kaseorg
6

Pari / GP , 137 octets, ~ 5 secondes

En utilisant les opérations de courbe elliptique intégrées de GP (et certains réglages de paramètres sournois) :

ecm(n)=iferr(if(n%2==0,2,n%3==0,3,for(a=1,n,ellmul(ellinit(Mod([a,a^2-a-1],n)),[1,a],lcm([1..ceil(4^a^0.5)])))),e,gcd(n,lift(Vec(e)[3])))

ecmest une fonction qui (devrait) retourner un facteur. Essayez-le en ligne!

Tester:

ecm(n)=iferr(if(n%2==0,2,n%3==0,3,for(a=1,n,ellmul(ellinit(Mod([a,a^2-a-1],n)),[1,a],lcm([1..ceil(4^a^0.5)])))),e,gcd(n,lift(Vec(e)[3])))

{
ns = [
  187,
  1679,
  14369648346682547857,
  34747575467581863011,
  52634041113150420921061348357,
  82312263010898855308580978867,
  205255454905325730631914319249,
  1233457775854251160763811229216063007,
  1751952685614616185916001760791655006749
  ]
}

test(n) = {
    d = ecm(n);
    if (!(1<d && d<n && n%d==0), error(d));
    print(n, ": ", d)
}

apply(test, ns)

quit

Non golfé:

ecm(n) = {
  iferr(if(n%2 == 0, 2,
           n%3 == 0, 3,
           for(a = 1, n,
               /* x^3 + A*x + B = y^2 */
               E = ellinit(Mod([a, a^2-a-1], n)); /* [A, B] */
               x0 = [1, a]; /* [x, y] */
               B = ceil(4^a^0.5); /* ~ exp(sqrt(log(p))), p ~= exp(a) */
               print("a=", a, ", B=", B);
               ellmul(E, x0, lcm([1..B]))
              )
          ),
         ERR, gcd(n, lift(Vec(ERR)[3] /* = Mod(d, n) */)),
         errname(ERR)=="e_INV")
}

Malheureusement, la gestion des facteurs 2 et 3 utilise de nombreux octets. Octets qui auraient pu être utilisés pour ajouter une étape 2:

ecm(n)=iferr(for(a=1,n,Y=X=ellmul(E=ellinit(Mod([a,1],n)),[0,1],(B=ceil(4^a^0.5))!);for(z=0,9*B,Y=elladd(E,Y,X))),e,gcd(n,lift(Vec(e)[3])))
japh
la source
1

Axiome, 137 octets 9 minutes

p(n:PI):PI==(j:=1;a:=3;s:=n^.2;repeat(b:=j:=nextPrime(j);repeat(b<s=>(b:=b*j);break);a:=powmod(a,b,n);d:=gcd(a-1,n);d>1 or j>n=>break);d)

au-dessus de la fonction p () qui implémenterait l'algorithme p-1 pour factoriser ci-dessous ce qu'il faut copier dans un fichier pour tester la fonction p ()

-- one has to copy this below text in a file name for example file.input
-- in one window where there is Axiom one could write 
-- )read C:\absolutepathwherethereisthatfile\file
-- and call the function test()
-- test()
-- the first character of all function and array must be afther a new line "\n"
)cl all
)time on
vA:=[187,1679,14369648346682547857,34747575467581863011,52634041113150420921061348357,82312263010898855308580978867,205255454905325730631914319249,1233457775854251160763811229216063007, 1751952685614616185916001760791655006749]

p(n:PI):PI==(j:=1;a:=3;s:=n^.2;repeat(b:=j:=nextPrime(j);repeat(b<s=>(b:=b*j);break);a:=powmod(a,b,n);d:=gcd(a-1,n);d>1 or j>n=>break);d)

-- this would try to factor n with p-1 Pollard method
pm1(n:PI):PI==
   j:=1;a:=3;s:=n^.2
   repeat
      b:=j:=nextPrime(j)
      repeat(b<s=>(b:=b*j);break)
      a:=powmod(a,b,n)
      d:=gcd(a-1,n);d>1 or j>n=>break
   d

test()==(for i in 1..#vA repeat output [vA.i, p(vA.i)])

résultats ici:

(5) -> test()
   [187,11]
   [1679,73]
   [14369648346682547857,9576890767]
   [34747575467581863011,9576890767]
   [52634041113150420921061348357,2860486313]
   [82312263010898855308580978867,311111111111113]
   [205255454905325730631914319249,2860486313]
   [1233457775854251160763811229216063007,1111111999999]
   [1751952685614616185916001760791655006749,36413321723440003717]
                                                               Type: Void
                              Time: 496.78 (EV) + 53.05 (GC) = 549.83 sec
RosLuP
la source
Pourriez-vous expliquer exactement comment exécuter ce code à partir de la ligne de commande dans ubuntu, s'il vous plaît? J'ai installé axiom et créé un fichier appelé foo.ax avec votre code non golfé.
@Lembik 1) renommer fop.ax dans foo.input 2) exécuter Axiom dans un terminal ou xterm 3) écrire dans ce terminal Axiom la commande suivante ") lire C: absolutepath \ foo" 4) écrire dans le terminal d'Axiom l'appel pour tester le fonctionnement (). Voici comment faire dans Windows, l'indice me semble ouvrir une session Axiom et charger le fichier avec la commande ") read"
RosLuP
@Lembik s'il y a un problème avec les fichiers, je pense que ce serait bien aussi: 1) exécuter Axiom 2) écrire) l'heure sur <return> dans le programme Axiom 3) copier-coller et appuyer sur retour dans chaque "copier-coller" dans le programme Axiom: le tableau vA, la fonction p () et test () 4) dans le test d'écriture du programme Axiom () <return>
RosLuP
@Lembik alors combien de temps cela prend-il?
RosLuP
1

Axiome, 10 minutes + 31 secondes

A(a)==>a:=(a*a+7)rem n;z(n)==(p:=a:=b:=101;for i in 1..repeat(A(a);A(b);A(b);p:=mulmod(p,a-b,n);i rem 999<9=>(p:=gcd(p,n);p>1=>break));p)

z () est la fonction rho, une fonction de 137 octets; ungolfed z () et appelez-le comme rho (). Il supposerait que gcd (0, n) = n donc la boucle s'arrête et revient pour échouer n.

)time on    
rho(n)==
  p:=a:=b:=101
  for i in 1..repeat
          A(a);A(b);A(b)
          p:=mulmod(p,a-b,n)
          i rem 999<9=>(p:=gcd(p,n);p>1=>break)
  p

va1:=[187,1679,14369648346682547857,34747575467581863011,52634041113150420921061348357,82312263010898855308580978867,205255454905325730631914319249,1233457775854251160763811229216063007, 1751952685614616185916001760791655006749]
p1()==(for i in 1..#va1-1 repeat output [va1.i,z(va1.i)]) 

les résultats (z () conviennent à tous, mais le dernier numéro 1751952685614616185916001760791655006749 n'est pas pris en compte (10 minutes))

(6) -> p1()
   [187,17]
   [1679,23]
   [14369648346682547857,1500450271]
   [34747575467581863011,3628273133]
   [52634041113150420921061348357,2860486313]
   [82312263010898855308580978867,264575131106459]
   [205255454905325730631914319249,2860486313]
   [1233457775854251160763811229216063007,1111111999999]
                                                               Type: Void
                                 Time: 30.38 (EV) + 1.38 (GC) = 31.77 sec

(8) -> z(1679)
   (8)  23
                                                    Type: PositiveInteger
                                                              Time: 0 sec
RosLuP
la source
0

Python 3 , 100 99 octets, 45 40 39 secondes + 10 minutes de pénalité

import math
def f(n):
 x=y=2;d=1
 while d<2:y=y*y+1;x,y=1+x*x%n,y*y%n+1;d=math.gcd(x-y,n)
 return d

Essayez-le en ligne!

Utilise Pollard-Rho avec la valeur initiale 2 et le polynôme x ^ 2 + 1.

plafond
la source
Vous pouvez utiliser pow(avec le 3e argument) pour améliorer votre vitesse d'exécution.
mbomb007