viernes, diciembre 02, 2011

Algoritmo extendido de Euclides

Haciendo algunos ejercicios criptográficos tenía que firmar digitalmente con elGamal los mensajes a enviar y para ello necesitaba calculo el inverso de a módulo n, así que:

os dejo un algoritmo para encontrar el inverso de a módulo n cuando mcd(a,n)=1.

     /// <summary>  
/// Algoritmo extendido de Euclides
/// </summary>
/// <returns>devuelve x tal que ax mod n=1, donde "0<a<n" ></returns>
static private int algoritmo(int a, int n)
{
List<int> g=new List<int>();
g.Add(n); g.Add(a);
List<int> u = new List<int>();
List<int> v = new List<int>();
u.Add(1); v.Add(0);
u.Add(0); v.Add(1);
int i = 1;
while (g[i] != 0)
{
//g[i] = u[i] * n + v[i] * a;
int y = g[i - 1] / g[i];
g.Add(g[i - 1] - y * g[i]);
u.Add(u[i - 1] - y * u[i]);
v.Add(v[i - 1] - y * v[i]);
i++;
}
int x = v[i - 1];
if (x > 0)
{ return x; }
else { return x + n; }
}

No hay comentarios:

Etiquetas

.net (1) ALGORITMO (4) algoritmos (1) Android (1) angular (2) aplicaciones WEB (1) ARGENTINA (1) ASP (4) asp .NET (1) ASP .NET Identity (1) attach (1) Azure (1) base de datos (1) BINDING (1) BioInformática (2) bootstrap (1) C (2) C# (27) castellano (1) catalán (1) Charla (1) CheckedListBox (1) Clase (1) clausura transitiva (2) CLIENTES (1) Closing (1) Combobox (1) Comisiones (1) CONCURSO (1) condones (1) consultas (1) corrupta (1) CORS OWIN (1) CORS WEB API 2 (1) Criptografía (1) CUENTA NARANJA (1) Custom Control (1) Daniel Seara (1) DATAGRIDVIEW (1) David Salgado (2) dendrograma (6) depurar (1) desarrollo (1) Deserializar (1) DEVCAMP (2) durex (1) e-DNI (1) el Guille (2) Eladio Rincón (1) elGamal (1) encriptación (1) encuesta (1) Entidad (1) ERROR (2) error 3624 (1) España (1) España es nido de víboras. (1) Euclides (1) Euclides extendido (1) evento (1) eventos. (1) factorización (1) factorizar (1) física (1) Framework 2.0 (1) Framework 3.5 (5) Framework 4 (2) Francisco González (1) Francisco Ruiz (1) GO (1) google (1) gossip (1) Grupos de usuarios (1) Guadalajara (1) Guille Comunity Tour (2) Gusenet (9) GUSENET. (1) Huelga informáticos (1) IBEX 35 (1) Idioma (1) IFT (1) IISExpress (1) Indice de Fuerza Tecnica (1) informática (1) Informix (1) ING DIRECT (1) INGDIRECT (1) Ingeniería Informática (2) Inteligencia artificial (5) Intro (1) IOS (1) IPad (1) IPhone (1) IV Aniversario (1) JavaScript (2) JPA (2) keybd_event (1) LA CAIXA (1) La Pineda (1) ladroentidad (1) Lector RSS (2) LINQ (5) LINQ2XML (1) ListBox (1) Live Distributed Objects (1) llenar (1) LOG (1) Madrid .NET (1) MainMenu (1) MAP (1) MAP 2011 (1) MAR DEL PLATA (1) matemáticas (1) Matriculación (1) MDIList (1) MdiWindowsListItem (1) MenuItem (1) MenuStrip (1) Microsoft (18) Microsoft Active Professional (1) Miguel Egea (2) MSDE 2 (1) MSDE 2000 (1) MVVM Light (2) mysql (1) NAMESPACE (1) Needleman (2) NET (1) NS (1) Oferta empleo (1) Office 14 (1) Office 2007 (1) Office 2009 (1) ON ERROR (1) OOB (1) Oscar Montesinos (1) OWIN (1) OWIN Security middleware (1) Paginación (1) PDC (1) Pedro Hurtado (1) PINTARTECA (1) PrinterSettings (1) Process (1) ProcessStartInfo (1) Programador (1) Relacional (1) robo (1) RSS (1) Rubén Garrigós (1) Salvador Ramos (1) Santa Pola (1) scrape (1) scraping (1) ScrollBar (1) Secretaría (1) SendInput (1) SENDKEYS (1) Sergio Vázquez (1) Serializar (1) Silverlight 2.0 (2) Silverlight 4 (1) Silverlight 5 (3) Silverlight. (1) Sindicado (1) Sistema Personal de Trading (3) Sistemas Distribuidos (1) SOLID SUMMIT 2009 (1) SPT (2) SQL Server (3) SQL Server 2000 (2) SQL Server 2005 (2) SQL Server 2008 (3) SQL Server Denali (1) SQL Server Information Services. (1) SQLU (1) SSIS (1) SUMMIT SQL (1) Suspect (1) Syndication (1) TAB (1) Tablas (1) Tarragona (1) Token bearer (1) ToolStripMenuItem (1) ToString() (1) Traductor (1) transacciones (1) treeview (1) truco (1) TRY CATCH (1) UCI (1) Unience (2) Universad (1) Universidad Oberta Catalunya (2) UOC (8) Usuarios. (1) VB (1) VB6 (1) VB9 (1) VIAJAR (1) Vila-seca (1) VISUAL BASIC (3) Visual Basic. (1) visual studio (1) Visual Studio 2005 (1) Visual Studio 2008 (16) Visual Studio 2010 (2) Visual Studio 2013 (1) VS2010 (1) VSTA (1) VSTO (1) WCF (1) WEB API (1) web.config (1) WebClient (1) WF (1) windows (1) Windows 7 (3) Windows 8 (2) Windows Azure (1) Windows pone (1) Windows Server 2008 (1) Windows Vista (1) woff (1) WP7 (1) WPF (1) Wunsch (2) XAML (4) XDocument (1) XElement (1) XML (3) XNA (1) Yield (2)