Apprendre Maple Index du Forum Apprendre Maple
Site dédié au logiciel de calcul formel Maple
 
  Page d'accueilPage d'accueil   FAQFAQ    RechercherRechercher    Liste des MembresListe des Membres    Groupes d'utilisateursGroupes d'utilisateurs 
S'enregistrerS'enregistrer    ProfilProfil   Se connecter pour vérifier ses messages privésSe connecter pour vérifier ses messages privés   ConnexionConnexion 

Ultime programme RSA ( Matrice et factorisation nbre 1er )
Aller à la page Précédente  1, 2, 3, 4, 5  Suivante
 
Poster un nouveau sujet   Répondre au sujet    Apprendre Maple Index du Forum -> Séquences, listes, ensembles, tables ou tableaux...
Voir le sujet précédent :: Voir le sujet suivant  
Auteur Message
ALS



Inscrit le: 11 Sep 2006
Messages: 647

MessagePosté le: 23 Oct 2014 7:46    Sujet du message: Répondre en citant

Bonjour,
C'est une multiplication à trous que vous vouliez faire dès le départ?
Moi, et avant moi zozo, n'avions pas du tout compris ça.
Je vous arrête tout de suite, cette méthode est irréaliste pour des nombres de grandes tailles : imaginez le nombre de boucles à effectuer et le nombre de variables à traiter!! Sûrement pas en temps polynômial à mon avis.
C'est bien pour ça qu'on met en place des algorithmes plus performants, ceux utilisés par ifactor. ifactor a un second argument facultatif , la méthode à utiliser. Voyez l'aide sur ifactor :

Citation:

Description
• ifactor returns the complete integer factorization of n.
• The answer is in the form u * ``(f[1])^e[1] * ... * ``(f[n])^e[n] such that
e[1] e[n]
n = u f[1] ... f[n]
where
u = sign(n)
,
f[1], ..., f[n]
are the distinct prime factors of n, and
e[1], ..., e[n]
are their multiplicities (negative in the case of the denominator of a rational).
• The expand function may be applied to cause the factors to be multiplied together again.
• If a second parameter is specified, the named method will be used when the front-end code fails to achieve the factorization. By default, a mixed method that primarily uses the multiple polynomial quadratic sieve method ('mpqsmixed') is used as the base method. Currently accepted names are:
'mpqs'
- Multiple Polynomial Quadratic Sieve method;
'morrbril'
- Morrison and Brillhart's continued fraction method;
'squfof'
- Shanks' undocumented square-free factorization;
'pollard'
- Pollard's rho method;
'lenstra'
- Lenstra's elliptic curve method;
'mpqsmixed'
- 'mpqs', 'morrbril' and 'pollard';
'mixed'
- 'morrbril' and 'pollard' (default for Maple 11 and earlier)
'easy'
- which does no further work; and
'easyfunc'
- which does no further work, and provides the computed factors.
• If the 'easy' option is chosen, the result of the ifactor call will be a product of the factors that were easy to compute, and one or more names of the form _c||m_n indicating an m-digit composite number that was not factored where the n is an integer which preserves (but does not imply) the uniqueness of this composite.
• If the 'easyfunc' option is chosen, the result of the ifactor call will be a product of the factors that were easy to compute, and one or more functions of the form _c_n(m) where the n is an integer which preserves the uniqueness of this composite, and m is the composite number itself.
The pollard base method accepts an additional optional integer k: ifactor(n, pollard, k). It increases the efficiency of the method when one of the factors is of the form
k m + 1
.


Pour une petite multiplication, à la rigueur ...
Dans votre exemple, pour le départ, on résout avec isolve (a*e mod 10) = 3 dans NxN. Si l'on veut a<e :

Code:

> s:=isolve((a*e mod 10)=3);  # résolution

  s := {a = -3, e = -1}, {a = -1, e = -3}, {a = 1, e = 3},

        {a = 3, e = 1}

> sol:={}:
> for k in s do
>   L:=NULL:
>   for i to 2 do if rhs(k[i])<0 then L:=L,rhs(k[i])+10 else L:=L,rhs(k[i]) end if end do:  # rajouter 10 si a ou e négatifs
>   if L[1]>L[2] then L:=L[2],L[1] end if:  # imposer a < e
>   L:=[L]: sol:= sol union {L}  # ajouter la solution [a,e]
> end do:
> sol;

                           {[1, 3], [7, 9]}




Je ne pourrai pas vous aider avant le 2 novembre, ça vous laisse le temps de réfléchir.

Bonne cogitation.
Revenir en haut de page
Voir le profil de l'utilisateur Envoyer un message privé
Guimzo



Inscrit le: 02 Juin 2012
Messages: 209

MessagePosté le: 23 Oct 2014 9:47    Sujet du message: Répondre en citant

Bonjour ALS,

Merci beaucoup déjà pour la nouvelle séquence, je vais l'essayer de suite : )
Entendu pour le 2 Novembre, et profitez alors de vos vacances, bien méritées ; j'aurais tellement aimé avoir un prof comme vous, mon prof de Math de Terminale S, n'était malheureusement pas vraiment un passionné : (
Mais quand on aime les chiffres, je crois que c'est éternel : )
Bonnes vacances, vous êtes mon héros : )

Mes 9 héros d'ailleurs :

Voltaire
Pascal
Molière
Apollinaire
Chopin
Socrate
Sœur Abraham ( Kirsten Stoffregen Pedersen une nonne que j'ai eu l'immense bonheur de rencontrer à Jérusalem )
Euler
ALS ( un prof de Math exceptionnel )

: )
Revenir en haut de page
Voir le profil de l'utilisateur Envoyer un message privé
ALS



Inscrit le: 11 Sep 2006
Messages: 647

MessagePosté le: 23 Oct 2014 13:18    Sujet du message: Répondre en citant

Merci, vraiment c'est trop.
J'ai aimé je pense avec passion ce métier d'enseignant.
Je ne suis plus en activité (de prof de CPGE en deuxième année) depuis un an, mais je continue à répondre sur ce site dédié à Maple.
Ca maintient les neurones actifs !
Revenir en haut de page
Voir le profil de l'utilisateur Envoyer un message privé
Guimzo



Inscrit le: 02 Juin 2012
Messages: 209

MessagePosté le: 24 Oct 2014 12:52    Sujet du message: Répondre en citant

Bonjour ALS,

C'est très sincère, vous êtes une personne qui inspire le respect et l'admiration, et je parie que vos élèves vous aimaient tous...
Pour la séquence, j'ai fait un dessin plus détaillé avec les explications, je l'ai téléchargé dans une boîte mail, j'ai dû faire comme ça parce que quand je poste une photo directement, l'image est trop petite après, et on voit pratiquement rien.
L'adresse c'est donc "maple-rsa@outlook.fr" et le mot de passe je vous l'envoie en MP à vous et zozo.
Il faudra donc simplement vous connecter via l'adresse mail et regarder après dans boîte de réception, merci et à bientôt ( 4 novembre...)
Revenir en haut de page
Voir le profil de l'utilisateur Envoyer un message privé
Guimzo



Inscrit le: 02 Juin 2012
Messages: 209

MessagePosté le: 25 Oct 2014 11:32    Sujet du message: Répondre en citant

Bonjour ALS et ZOZO,

J'ai posté dans la boîte mail un schéma complet pour un nombre à 3 digits, et un dessin sur une méthode japonaise de multiplication qui est très intéressante pour les factorisations.

Adresse mail : " maple-rsa@outlook.fr "
Mot de passe c'est celui que je vous ai envoyé en MP.

Maintenant je vais réfléchir à comment mettre tout ça en langage Maple, et voir quelles sont les autres techniques de multiplications de nombres, en particulier, me pencher sur la technique japonaise avec des lignes.
Bon week end à vous, à bientôt
Revenir en haut de page
Voir le profil de l'utilisateur Envoyer un message privé
Guimzo



Inscrit le: 02 Juin 2012
Messages: 209

MessagePosté le: 25 Oct 2014 17:07    Sujet du message: Répondre en citant

https://fbcdn-sphotos-e-a.akamaihd.net/hphotos-ak-xaf1/v/t1.0-9/10610690_738526182861986_4961945181833045921_n.jpg?oh=d4a620fb0a5d45ad4a145fc78255b66a&oe=54E0ACB4&__gda__=1425313029_5b4e85f0d7f88ce10e99e074c6a0be81
Revenir en haut de page
Voir le profil de l'utilisateur Envoyer un message privé
ALS



Inscrit le: 11 Sep 2006
Messages: 647

MessagePosté le: 02 Nov 2014 9:55    Sujet du message: Répondre en citant

Bonjour,

Après cette semaine de vacances en Bretagne Sud sous un soleil exceptionnel, j'ai réfléchi à conceptualiser un algorithme de retour arrière (backtracking) dans le cas général pour votre problème.

J'ai essayé de me baser sur l'algorithme de retour arrière que j'avais programmé pour le sudoku comme ici (procédure solution):
http://alamanya.free.fr/themes/sudoku.htm
mais ça me semble très difficilement transposable à votre problème, car il y a trop de paramètres, de plus le problème des retenues vient corser la difficulté.

Qui vous demande de programmer ça? C'est dans le cadre de vos études?

Sorry !
Revenir en haut de page
Voir le profil de l'utilisateur Envoyer un message privé
ALS



Inscrit le: 11 Sep 2006
Messages: 647

MessagePosté le: 03 Nov 2014 8:44    Sujet du message: Répondre en citant

Bonjour,
Sinon, il y a l'algorithme classique de factorisation (mais il est lent pour les grandes valeurs de n):

Code:

> decomposer:=proc(n::posint)
> local d,i,m,facteur;
>   d := 3; facteur:=NULL: m:=n:
>   while (m mod 2 = 0) do
>     facteur:=facteur,2;
>     m := m / 2;
>   end do:
>   while (d * d <= m) do
>     if (m mod d = 0) then
>       facteur:=facteur,d;
>       m := m / d;
>     else
>       d := d + 2
>     end if;
>  end do:
>   if (m > 1) then   
>      facteur:=facteur,m;
>   end if:
>   [facteur];
> end proc:

> decomposer(16195393);

                             [3769, 4297]

Revenir en haut de page
Voir le profil de l'utilisateur Envoyer un message privé
ALS



Inscrit le: 11 Sep 2006
Messages: 647

MessagePosté le: 06 Nov 2014 12:29    Sujet du message: Répondre en citant

Pour la multiplication de deux nombres premiers de longueur 3, la petite séquence suivante d'instructions donne assez rapidement le résultat:

Code:


> N:=85073:
> for a from 0 to 9 do
>   for b from 0 to 9 do
>     for c from 0 to 9 do
>       if 100*c+10*b+a>1 and is(N/(100*c+10*b+a),integer) then print(100*c+10*b+a,N/(100*c+10*b+a)): break fi
>     od
>   od
> od:

                               241, 353

                               353, 241




On peut étendre à des longueurs supérieures en rajoutant des boucles for d ... for e ... etc ... et en adaptant: 1000*d+100*c+10*b+a, ... 10000*e+1000*d+100*c+10*b+a, ... etc ...

Ce sera très long dès que la longueur des diviseurs premiers augmentera.

Cet algorithme ainsi que celui du message précédent peuvent être qualifiés de "naïfs", car ils passent en revue toutes les possibilités éventuelles.
Revenir en haut de page
Voir le profil de l'utilisateur Envoyer un message privé
Guimzo



Inscrit le: 02 Juin 2012
Messages: 209

MessagePosté le: 09 Nov 2014 19:14    Sujet du message: Répondre en citant

Bonjour ALS,

Je suis ravi de vous revoir sur le forum, et très content pour vos vacances en Bretagne : )
Je reçois cette semaine la famille de ma femme, donc malheureusement, je dois "laisser" pour 2 petits jours "mes chers nombres premiers" de côté.. : )
En tout cas merci, et je vais quand même essayer la séquence que vous avez fait pour des facteurs de 3 digits ; je pense que l'on passe sans la commande "ifactor", ce qui est très bien !
Pour des facteurs plus grands, je ne pense pas qu'il faille essayer toutes les possibilités, puisque à la base on part toujours de 2 couples de possibilités qui conduisent forcément à d'autres possibilités bien précises...

Je voulais vous parler aussi de cette autre méthode de multiplication qui peut-être serait plus simple à mettre en programme de façon à factoriser des nombres entiers :

4 2*
2 3
---------------------------
12 6
8 4 0
________________________
8 16 6

Donc est-ce que ce serait plus simple à construire un programme, qui permettrait de trouver les nombres "8", "16" et "6"....?
Enfin, cela reste à voir, mais pour la séquence que vous avez fait et qui n'utilise en tout cas pas "ifactor" c'est très bien.
À très bientôt,
Revenir en haut de page
Voir le profil de l'utilisateur Envoyer un message privé
Guimzo



Inscrit le: 02 Juin 2012
Messages: 209

MessagePosté le: 09 Nov 2014 19:22    Sujet du message: Répondre en citant

Re-bonjour ALS,


Un léger soucis avec la séquence, la réponse de Maple :

" Error, numeric exception: division by zero "

================================
N := 85073; for a from 0 to 9 do for b from 0 to 9 do for c from 0 to 9 do if `and`(100*c+10*b+a > 1, is(N/(100*c+10*b+a), integer)) then print(100*c+10*b+a, N/(100*c+10*b+a)); break end if end do end do end do
============================
Revenir en haut de page
Voir le profil de l'utilisateur Envoyer un message privé
Guimzo



Inscrit le: 02 Juin 2012
Messages: 209

MessagePosté le: 13 Nov 2014 20:43    Sujet du message: Répondre en citant

Bonjour ALS,

De retour : )
Alors j'ai rajouté cette ligne pour éviter "l'exception division par zéro" mais toujours la même erreur :

================
remember N/(0)=infinity;
=================
Revenir en haut de page
Voir le profil de l'utilisateur Envoyer un message privé
Guimzo



Inscrit le: 02 Juin 2012
Messages: 209

MessagePosté le: 13 Nov 2014 20:52    Sujet du message: Répondre en citant

Re-bonsoir ALS,

J'ai mis le compteur de 1 à 9 pour éviter la division par zéro ; ça fonctionne quand les facteurs n'ont pas un "0" dans leur écriture, du genre 241 ou 353 mais quand les facteurs ont un "0" dans leur écriture, ça ne fonctionne pas : (......?
Revenir en haut de page
Voir le profil de l'utilisateur Envoyer un message privé
Guimzo



Inscrit le: 02 Juin 2012
Messages: 209

MessagePosté le: 13 Nov 2014 21:21    Sujet du message: Répondre en citant

Rebonsoir ALS,

J'ai essayé avec des facteurs de 6 chiffres ( mais qui n'ont pas de "0" dans leur écriture, ça marche avec un temps de 53 secondes ) ; je vais essayer de monter le nombre de digits des facteurs pour voir

====================================
N := 15515306203;
for a from 1 to 9 do
for b from 1 to 9 do
for c from 1 to 9 do
for d from 1 to 9 do
for e from 1 to 9 do
for f from 1 to 9 do
if `and`(100000*f+10000*e+1000*d+100*c+10*b+a > 1, is(N/(100000*f+10000*e+1000*d+100*c+10*b+a), integer)) then print(100000*f+10000*e+1000*d+100*c+10*b+a, N/(100000*f+10000*e+1000*d+100*c+10*b+a)); break end if end do end do end do end do end do end do
==================================
Revenir en haut de page
Voir le profil de l'utilisateur Envoyer un message privé
ALS



Inscrit le: 11 Sep 2006
Messages: 647

MessagePosté le: 14 Nov 2014 7:18    Sujet du message: Répondre en citant

Bonjour,
Ne pas utiliser la forme binaire du and, sinon vous avez l'erreur de division par zéro.


Code:


> N := 15515306203;
> for a from 0 to 9 do
> for b from 0 to 9 do
> for c from 0 to 9 do
> for d from 0 to 9 do
> for e from 0 to 9 do
> for f from 0 to 9 do
> if 100000*f+10000*e+1000*d+100*c+10*b+a > 1 and is(N/(100000*f+10000*e+1000*d+100*c+10*b+a), integer) then print(100000*f+10000*e+1000*d+100*c+10*b+a, N/(100000*f+10000*e+1000*d+100*c+10*b+a)); break end if end do end do end do end do end do end do:


                           N := 15515306203


                            123941, 125183


                            125183, 123941

Revenir en haut de page
Voir le profil de l'utilisateur Envoyer un message privé
Montrer les messages depuis:   
Poster un nouveau sujet   Répondre au sujet    Apprendre Maple Index du Forum -> Séquences, listes, ensembles, tables ou tableaux... Toutes les heures sont au format GMT + 2 Heures
Aller à la page Précédente  1, 2, 3, 4, 5  Suivante
Page 3 sur 5

 
Sauter vers:  
Vous ne pouvez pas poster de nouveaux sujets dans ce forum
Vous ne pouvez pas répondre aux sujets dans ce forum
Vous ne pouvez pas éditer vos messages dans ce forum
Vous ne pouvez pas supprimer vos messages dans ce forum
Vous ne pouvez pas voter dans les sondages de ce forum


phpBB

Développé par phpBB © 2001, 2006 phpBB Group
Traduction par : phpBB-fr.com


Apprendre Maple - ©  - Alain Le Stang - Navigation optimisée pour une résolution 1024 x 768.