Counting points on algebraic curves over finite fields has\u00a0numerous applications in communications and cryptology, and has led\u00a0to some of the most beautiful results in 20th century arithmetic\u00a0geometry. A natural generalization is to count the number of points\u00a0over prime power rings, e.g., the integers modulo a prime power.\u00a0However, the theory behind the latter kind of point counting began\u00a0more recently and there are numerous gaps in our algorithmic knowledge.<\/p>\n
We give a simple combinatorial construction that reduces point\u00a0counting over prime power point counting to the prime field case. In\u00a0particular, for any bivariate polynomial f in Z[x,y] and positive\u00a0integers p and k with p prime, we show how one can count the number\u00a0of roots of f in (Z\/(p^k))^2 in time p^{1\/2 + o(1)} (dk)^{O(1)},\u00a0and even faster for certain curves. This generalizes earlier results\u00a0of Cheng, Lecerf, Saxena, and Wan in the univariate case, and simplifies\u00a0earlier work of Denef, Igusa, and Veys on local zeta functions.<\/p>\n
This is joint work with Caleb Robelle and Yuyu Zhu.<\/p>\n","protected":false},"excerpt":{"rendered":"
Counting points on algebraic curves over finite fields has\u00a0numerous applications in communications and cryptology, and has led\u00a0to some of the most beautiful results in 20th century arithmetic\u00a0geometry. A natural generalization […]<\/p>\n","protected":false},"author":73,"featured_media":0,"template":"","meta":{"_acf_changed":false,"_price":"","_stock":"","_tribe_ticket_header":"","_tribe_default_ticket_provider":"","_tribe_ticket_capacity":"0","_ticket_start_date":"","_ticket_end_date":"","_tribe_ticket_show_description":"","_tribe_ticket_show_not_going":false,"_tribe_ticket_use_global_stock":"","_tribe_ticket_global_stock_level":"","_global_stock_mode":"","_global_stock_cap":"","_tribe_rsvp_for_event":"","_tribe_ticket_going_count":"","_tribe_ticket_not_going_count":"","_tribe_tickets_list":"[]","_tribe_ticket_has_attendee_info_fields":false,"_tribe_events_status":"","_tribe_events_status_reason":"","_tribe_events_is_hybrid":"","_tribe_events_is_virtual":"","_tribe_events_virtual_video_source":"","_tribe_events_virtual_embed_video":"","_tribe_events_virtual_linked_button_text":"","_tribe_events_virtual_linked_button":"","_tribe_events_virtual_show_embed_at":"","_tribe_events_virtual_show_embed_to":[],"_tribe_events_virtual_show_on_event":"","_tribe_events_virtual_show_on_views":"","_tribe_events_virtual_url":"","footnotes":"","_tec_slr_enabled":"","_tec_slr_layout":""},"tags":[],"tribe_events_cat":[13],"class_list":["post-1347","tribe_events","type-tribe_events","status-publish","hentry","tribe_events_cat-antc-seminar","cat_antc-seminar"],"acf":[],"yoast_head":"\n