Computing class polynomials with the Chinese Remainder Theorem

Channel:
Microsoft Research
Subscribers:
344,000
Published on ● Video Link: https://www.youtube.com/watch?v=5tmYyj3dK7U


Duration: 59:53
634 views
5

Class polynomials play a key role in the CM-method for constructing elliptic curves with known order. This has many applications to cryptography and is the primary means of obtaining pairing-friendly curves. The CM-method is unfortunately constrained by practical limits on the size of the CM discriminant, with |D| < 10^10 an accepted upper bound. I will present a new algorithm, based on the CRT-approach to computing Hilbert class polynomials [Belding-Broker-Enge-Lauter 2008], one that is faster than existing methods and able to handle much larger discriminants. For suitable D, this algorithm can also compute class polynomials for more favorable class invariants (derived from those of Weber and Ramanujan), yielding a further improvement in the constant factors. These results have been used to construct many pairing-friendly curves with large CM-discriminant, including examples with |D| > 10^14.



Other Videos By Microsoft Research


2016-09-08Practical Genius: The Real Smarts You Need to Get Your Passions and Talents Working for You
2016-09-08The Quest: Energy, Security, and the Remaking of the Modern World
2016-09-08How TodayΓÇÖs Entrepreneurs Use Continuous Innovation to Create Radically Successful Businesses
2016-09-08The Infinity Puzzle: Quantum Field Theory and the Hunt for an Orderly Universe
2016-09-08In the Plex: How Google Thinks, Works, and Shapes Our Lives
2016-09-08When Gadgets Betray Us: The Dark Side of our Infatuation with New Technologies
2016-09-08Modernist Cuisine: The Art and Science of Cooking
2016-09-08An Optimist's Tour of the Future: One Curious Man Sets Out to Answer What's
2016-09-08The Net Delusion: The Dark Side of Internet Freedom
2016-09-08A Rigorous Perspective on Liouville Quantum Gravity & KPZ
2016-09-08Computing class polynomials with the Chinese Remainder Theorem
2016-09-08Theory Plus Practice in Computer Security: Radio Frequency Identification and Whitebox Fuzzing [1/4]
2016-09-08Why the Rich Get Richer, Cheaters Get Caught and Your Neighbor Usually Looks Like You [1/2]
2016-09-08Embedded Memory in Nanometer Regime
2016-09-08Incentivizing Outsourced Computation
2016-09-08Random Sorting Networks
2016-09-08SOLAR REVOLUTION: THE ECONOMIC TRANSFORMATION OF THE GLOBAL ENERGY INDUSTRY
2016-09-08Are You Ready to Succeed? Unconventional Strategies to Achieving Mastery in Business and Life [1/2]
2016-09-08Counting independent sets up to the tree threshold
2016-09-08Randomly coloring planar graphs with fewer colors than the maximum degree
2016-09-07Drop Dead Healthy: One Man's Humble Quest for Bodily Perfection


Tags:
microsoft research