Cocientes notablesDe Wikipedia, la enciclopedia libreSaltar a: navegacin, bsqueda No debe confundirse con Productos notables.Los cocientes notables son aquellos que sin efectuar la divisin se puede escribir su desarrollo. Se caracterizan por ser siempre cocientes exactos, es decir, igual a cero.

Forma general de un cociente notablendice[ocultar] 1 Casos de un cociente notables 1.1 Caso 1 1.2 Caso 2 1.3 Caso 3 1.4 Caso 4 (No es un cociente notable) 2 Propiedades 2.1 Nmero de trminos de desarrollo 2.2 Clculo del trmino k-simo 3 Enlaces externos 4 Vase tambin

[editar] Casos de un cociente notablesExisten 3 casos de cocientes notables:[editar] Caso 1Este caso se produce cuando n es un nmero par o impar.

[editar] Caso 2Este caso se produce cuando n es un nmero par.

[editar] Caso 3Este caso se produce cuando n es un nmero impar.

[editar] Caso 4 (No es un cociente notable)Este caso se produce siendo n un nmero par o impar en dicho desarrollo no se genera un cociente notable, ya que posee residuo:.

[editar] PropiedadesSlo si es un cociente notable, se cumple las siguientes propiedades[editar] Nmero de trminos de desarrolloPara hallar el nmero de trminos que va a tener la solucin de la divisin, por ejemplo de:

Se calcula como la divisin de los exponentes de la misma variable:

[editar] Clculo del trmino k-simoSi te piden el trmino lugar o posicin k, del siguiente cociente notable:

Entonces "tk" se calcula de la siguiente manera:

Notas: En esta propiedad si k ocupa un nmero de trmino par (como segundo o cuarto), se coloca el signo -; y si k ocupa un nmero de trmino impar, el signo es + En esta propiedad n simboliza el nmero de trminos del desarrollo.[editar] Enlaces externos Ediciones Rubios - lgebra - Cocientes notables. lgebra bsica - Cocientes notables.

Factorizacin de enterosDe Wikipedia, la enciclopedia libreSaltar a: navegacin, bsqueda En teora de nmeros, la factorizacin de enteros o factorizacin de primos consiste en descomponer un nmero compuesto (no primo) en divisores no triviales, que cuando se multiplican dan el nmero original.Cuando los nmeros son muy grandes no se conoce ningn algoritmo que resuelva eficientemente este problema; un reciente intento de factorizar un nmero de 200 dgitos (RSA-200) tard 18 meses y consumi ms de medio siglo de tiempo de clculo. Su supuesta dificultad es el ncleo de ciertos algoritmos criptogrficos, como el RSA. Muchas reas de las matemticas y de las ciencias de la computacin, como la teora algebraica de nmeros, las curvas elpticas o la computacin cuntica, estn relacionadas con este problema.Descomponer dos nmeros de igual longitud no tiene por qu tener la misma complicacin. Actualmente (2006) se considera que los casos ms duros son aquellos para los que los factores son dos nmeros primos, elegidos al azar, de aproximadamente el mismo tamao.ndice[ocultar] 1 Descomposicin en factores primos 2 Factorizacin de enteros en tiempo polinmico 2.1 Aplicaciones prcticas 3 Estado actual 3.1 Dificultad y complejidad 4 Algoritmos de factorizacin 4.1 De propsito general 4.2 De propsito especfico 4.3 Otros algoritmos importantes 5 Vase tambin 6 Referencias 6.1 Bibliografa 7 Enlaces externos 7.1 En espaol 7.2 En ingls

[editar] Descomposicin en factores primos

La imagen demuestra la descomposicin en primos del nmero 864. Un mtodo rpido de escribir el resultado en nmeros primos es .Por el teorema fundamental de la aritmtica, cada entero positivo tiene una nica descomposicin en nmeros primos. La mayor parte de los algoritmos de factorizacin elementales son de propsito general, es decir, permiten descomponer cualquier nmero introducido, y solo se diferencian sustancialmente en el tiempo de ejecucin.[editar] Factorizacin de enteros en tiempo polinmicoEl problema de factorizar enteros en tiempo polinmico no ha sido an resuelto. Si alguien lo consiguiera, esto tendra gran inters en el mbito de la criptografa, ya que muchos criptosistemas dependen de su imposibilidad. En medios acadmicos, la existencia de tal avance sera una gran noticia; en otros crculos, sera un gran secreto, por razones obvias.[editar] Aplicaciones prcticasLa dureza de este problema, se encuentra en el ncleo de varios sistemas criptogrficos importantes. Un algoritmo veloz para la factorizacin de enteros significara que el algoritmo de clave pblica RSA es inseguro. Algunos sistemas criptogrficos, como el algoritmo de clave pblica Rabin y el generador de nmeros pseudoaleatorios Blum Blum Shub garantizaran una mejora en su seguridad; cualquier mtodo que logre quebrarlos puede ser utilizado para crear un algoritmo de factorizacin ms veloz; si la factorizacin de enteros es veloz, stos se vuelven ms duros. En contraste, pueden existir ataques ms eficientes al problema RSA, pero no se conoce ninguno.Un problema duro similar con aplicaciones criptogrficas es el problema del logaritmo discreto.[editar] Estado actualUn equipo en la Agencia Federal Alemana para Seguridad de Tecnologa de Informacin (BSI) sostiene el rcord por factorizacin de semiprimos en la serie propuesta por la Competicin de factorizacin RSA, con patrocinio de RSA Security. El 9 de mayo de 2005, este equipo anunci la factorizacin de RSA-200, un nmero de 663 bits, usando la criba general del cuerpo de nmeros.El mismo equipo ms tarde anunci la factorizacin de RSA-640, un nmero ms pequeo, conteniendo 193 digitos decimales (640 bits) el 4 de noviembre de 2005.Ambas factorizaciones requirieron varios meses de tiempo de computadoras, utilizando el poder combinado de 80 CPUs Opteron AMD.[editar] Dificultad y complejidadSi un nmero grande, de b bits es el producto de dos primos de aproximadamente el mismo tamao, no existe algoritmo conocido capaz de factorizarlo en tiempo polinomial. Esto significa que ningn algoritmo conocido puede factorizarlo en tiempo O(bk), para cualquier constante k. Aunque, existen algoritmos que son ms rpidos que O(ab) para cualquier a mayor que 1. En otras palabras, los mejores algoritmos son sper-polinomiales, pero sub-exponenciales. En particular, el mejor tiempo asinttico de ejecucin es el del algoritmo de criba general del cuerpo de nmeros (CGCN), que para un nmero n es:

Para una computadora ordinaria, la CGCN es el mejor algoritmo conocido para nmeros grandes. Para una computadora cuntica, en cambio, Peter Shor descubri en 1994 un algoritmo que lo resuelve en tiempo polinmico. Esto tendra implicaciones importantes en la criptografa, si alguna vez se construyese una computadora cuntica. El algoritmo de Shor slo tarda un tiempo O((log n)3) y ocupa un espacio O(log n). En 2001, la primera computadora cuntica de 7 cubits fue la primera en correr el algoritmo de Shor. Factoriz el nmero 15.No se conoce exactamente cuales clases de complejidad contienen el problema de factorizacin de enteros. Se sabe que su forma de decisin-problema ("Tiene N un factor menor que M?") tiene complejidad NP y co-NP. Esto es porque tanto respuestas SI y NO pueden ser comprobadas si se proveen los factores primos junto a sus certificados de primalidad. Se conoce que est en BQP gracias al algoritmo de Shor. Se sospecha que se encuentra fuera de las tres clases de complejidad (P, NP Completo, co-NP Completo). Si fuese posible probar que se encuentra en cualquiera de estas dos ltimas, eso implicara que NP = co-NP. Ese sera un resultado muy sorprendente, y por ello se sospecha ampliamente que la factorizacin de enteros se encuentra fuera de ambas. Mucha gente ha intentado encontrar algoritmos clsicos de tiempo polinomial para esta, y ha fallado; por esto se sospecha que se encuentra fuera de P. Otro problema en NP pero que no se cree que sea P o NP Completo es el problema de isomorfismo de grafo.Interesantemente, el problema de decisin "es N un nmero compuesto?" (o lo que es igual: "es N un nmero primo?") parece ser mucho ms sencillo que el problema de encontrar los factores enteros en los que se descompone N. En concreto, el primer problema puede ser resuelto en tiempo polinnico (sobre el nmero n de cifras de N), de acuerdo a un reciente artculo referenciado ms adelante. Adems, existen varios algoritmos aleatorios que pueden comprobar la primalidad de un nmero muy rpidamente, si se est dispuesto a aceptar una pequea posibilidad de error. La facilidad de la prueba de primalidad es una parte crucial del algoritmo RSA, puesto que es necesaria para encontrar nmeros primos grandes.[editar] Algoritmos de factorizacin[editar] De propsito generalEl tiempo de ejecucin de un algoritmo de factorizacin de propsito general depende solamente del tamao del entero a factorizar. ste es el tipo de algoritmo usado para factorizar nmeros RSA. La mayora de algoritmos de factorizacin de propsito general estn basados en el mtodo de congruencia de cuadrados. A continuacin se listan algunos de los algoritmos de propsito general ms conocidos: Algoritmo de Dixon Factorizacin con fracciones continuas Criba cuadrtica Criba racional Algoritmo general de criba del cuerpo de nmeros Factorizacin de formas cuadradas de Shanks[editar] De propsito especficoEl tiempo de ejecucin de un algoritmo de factorizacin de propsito especfico depende de las propiedades de sus factores desconocidos: tamao, forma especial, etc. Dichos factores cambian de un algoritmo a otro. Divisin por tentativa Algoritmo rho de Pollard Algoritmo p-1 de Pollard Algoritmo p+1 de Williams Factorizacin de curva elptica de Lenstra Mtodo de factorizacin de Fermat Mtodo de factorizacin de Euler Algoritmo especial de criba del cuerpo de nmeros[editar] Otros algoritmos importantes Algoritmo de Shor, para computadores cunticos