Est-ce que PARI/GP a une fonction pour trouver le plus petit facteur premier d'un t_INT ou sinon effectuer une factorisation partielle d'un nombre entier?Fonction pour trouver le facteur premier le moins
Par exemple, si je le numéro:
a=261432792226751124747858820445742044652814631500046047326053169701039080900441047539208779404889565067
il faut beaucoup de temps pour le faire parce que factor(a)a contient deux énormes facteurs premiers. Cependant, il est assez facile de trouver que 17 est un diviseur de a.
Bien sûr, dans ce cas, j'aurais pu utiliser seulement forprime(p=2,,a % p == 0 && return(p)) ou une division d'essai similaire pour trouver le facteur. Mais si le moindre facteur avait eu 20 chiffres décimaux, disons, ce serait impraticable, et j'aurais pu vouloir utiliser les méthodes sophistiquées de factor dans ce cas.
Il serait donc idéal si je pouvais appeler factor avec une sorte de drapeau disant que je serai heureux avec une factorisation partielle, ou de dire que tout ce que je me soucie de est le plus petit diviseur non trivial, etc.
Avez-vous pensé à une variante de la [factorisation de la courbe elliptique de Lenstra] (https://en.wikipedia.org/wiki/Lenstra_elliptic-curve_factorization) (qui se spécialise dans l'obtention de petits facteurs)? Vous pouvez le modifier pour casser une fois qu'il a trouvé un facteur. –
@JosephWood La fonction 'factor' ou' factorint' de PARI utilise déjà des méthodes elliptiques comme l'une de ses approches. Je sais que je pourrais coder ma propre implémentation de courbe elliptique, mais je demandais s'il y avait quelque chose de intégré dans PARI/GP. –
La bibliothèque PARI a la fonction 'Z_factor_until' qui pourrait être utile. Mais prouver que vous avez trouvé le plus petit facteur premier n'est généralement pas facile, choisissez une option: ne fonctionne qu'avec des nombres spéciaux, certains avec une probabilité élevée plutôt qu'avec certitude; longue durée de fonctionnement; ne fonctionne que sur de petits nombres. – Charles